{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Collect Coins in a Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #graph #topological-sort #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #图 #拓扑排序 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: collectTheCoins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #收集树中金币"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n</code>&nbsp;个节点的无向无根树，节点编号从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。给你整数&nbsp;<code>n</code>&nbsp;和一个长度为 <code>n - 1</code>&nbsp;的二维整数数组 <code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示树中节点&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条边。再给你一个长度为 <code>n</code>&nbsp;的数组&nbsp;<code>coins</code>&nbsp;，其中&nbsp;<code>coins[i]</code> 可能为&nbsp;<code>0</code>&nbsp;也可能为&nbsp;<code>1</code>&nbsp;，<code>1</code>&nbsp;表示节点 <code>i</code>&nbsp;处有一个金币。</p>\n",
    "\n",
    "<p>一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>收集距离当前节点距离为 <code>2</code>&nbsp;以内的所有金币，或者</li>\n",
    "\t<li>移动到树中一个相邻节点。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。</p>\n",
    "\n",
    "<p>如果你多次经过一条边，每一次经过都会给答案加一。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/03/01/graph-2.png\" style=\"width: 522px; height: 522px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/03/02/graph-4.png\" style=\"width: 522px; height: 522px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == coins.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= coins[i] &lt;= 1</code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li><code>edges</code>&nbsp;表示一棵合法的树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [collect-coins-in-a-tree](https://leetcode.cn/problems/collect-coins-in-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [collect-coins-in-a-tree](https://leetcode.cn/problems/collect-coins-in-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,0,0,0,1]\\n[[0,1],[1,2],[2,3],[3,4],[4,5]]', '[0,0,0,1,1,0,0,1]\\n[[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        # remove leaf nodes with the role: \n",
    "        # If a leaf node's coin is 0, remove it\n",
    "        # If a leaf node's coin is 1, remove it and set its neighbours' coins to max(2, coin)\n",
    "        # If a leaf node's coin is 2, moreve it and set its neighbours' coins to max(3, coin)\n",
    "        # n edges x2\n",
    "        n = len(coins)\n",
    "        node_edges = [[] for _ in coins]\n",
    "        for edge in edges:\n",
    "            node_edges[edge[0]] += [edge[1]]\n",
    "            node_edges[edge[1]] += [edge[0]]\n",
    "        \n",
    "        n_removed_nodes = 0\n",
    "        while True:\n",
    "            updated = False\n",
    "            for i in range(n):\n",
    "                if len(node_edges[i]) == 1: # is leaf node\n",
    "                    neighbour = node_edges[i][0]\n",
    "                    if coins[i] == 0:\n",
    "                        node_edges[neighbour].remove(i)\n",
    "                        node_edges[i] = []\n",
    "                        updated = True\n",
    "                        n_removed_nodes += 1\n",
    "                    if coins[i] == 1:\n",
    "                        coins[neighbour] = max(coins[neighbour], 2)\n",
    "                        node_edges[neighbour].remove(i)\n",
    "                        node_edges[i] = []\n",
    "                        updated = True\n",
    "                        n_removed_nodes += 1\n",
    "                    if coins[i] == 2:\n",
    "                        coins[neighbour] = max(coins[neighbour], 3)\n",
    "                        node_edges[neighbour].remove(i)\n",
    "                        node_edges[i] = []\n",
    "                        updated = True\n",
    "                        n_removed_nodes += 1\n",
    "            if not updated:\n",
    "                break\n",
    "\n",
    "        return (n-n_removed_nodes-1) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        indeg = [0] * n\n",
    "\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            indeg[a] += 1\n",
    "            indeg[b] += 1\n",
    "        \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 1 and coins[i] == 0: q.append(i)\n",
    "        \n",
    "        cnt = 0\n",
    "        while q:\n",
    "            ver = q.popleft()\n",
    "            indeg[ver] -= 1\n",
    "            cnt += 1\n",
    "            for b in g[ver]:\n",
    "                indeg[b] -= 1\n",
    "                if indeg[b] == 1 and coins[b] == 0: q.append(b)\n",
    "\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 1: q.append(i)\n",
    "\n",
    "        for _ in range(2):\n",
    "            for _ in range(len(q)):\n",
    "                ver = q.popleft()\n",
    "                cnt += 1\n",
    "                for b in g[ver]:\n",
    "                    indeg[b] -= 1\n",
    "                    if indeg[b] == 1:\n",
    "                        q.append(b)\n",
    "        return max(0, (n - cnt - 1) * 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "        deg = list(map(len, g))  # 每个节点的度数（邻居个数）\n",
    "\n",
    "        left_edges = n - 1  # 剩余边数\n",
    "        # 拓扑排序，去掉没有金币的子树\n",
    "        q = []\n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "            if d == 1 and c == 0:  # 没有金币的叶子\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            left_edges -= 1  # 删除节点到其父节点的边\n",
    "            for y in g[q.pop()]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1 and coins[y] == 0:  # 没有金币的叶子\n",
    "                    q.append(y)\n",
    "\n",
    "        # 再次拓扑排序\n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "            if d == 1 and c:  # 有金币的叶子（判断 c 是避免把没有金币的叶子也算进来）\n",
    "                q.append(i)\n",
    "        left_edges -= len(q)  # 删除所有叶子（到其父节点的边）\n",
    "        for x in q:  # 遍历所有叶子\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1:  # y 现在是叶子了\n",
    "                    left_edges -= 1  # 删除 y（到其父节点的边）\n",
    "        return max(left_edges * 2, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\r\n",
    "        n = len(coins)\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)  # 建图\r\n",
    "        deg = list(map(len, g))  # 每个节点的度数（邻居个数）\r\n",
    "\r\n",
    "        left_edges = n - 1  # 剩余边数\r\n",
    "        # 拓扑排序，去掉没有金币的子树\r\n",
    "        q = []\r\n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\r\n",
    "            if d == 1 and c == 0:  # 没有金币的叶子\r\n",
    "                q.append(i)\r\n",
    "        while q:\r\n",
    "            left_edges -= 1  # 删除节点到其父节点的边\r\n",
    "            for y in g[q.pop()]:\r\n",
    "                deg[y] -= 1\r\n",
    "                if deg[y] == 1 and coins[y] == 0:  # 没有金币的叶子\r\n",
    "                    q.append(y)\r\n",
    "\r\n",
    "        # 再次拓扑排序\r\n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\r\n",
    "            if d == 1 and c:  # 有金币的叶子（判断 c 是避免把没有金币的叶子也算进来）\r\n",
    "                q.append(i)\r\n",
    "        left_edges -= len(q)  # 删除所有叶子（到其父节点的边）\r\n",
    "        for x in q:  # 遍历所有叶子\r\n",
    "            for y in g[x]:\r\n",
    "                deg[y] -= 1\r\n",
    "                if deg[y] == 1:  # y 现在是叶子了\r\n",
    "                    left_edges -= 1  # 删除 y（到其父节点的边）\r\n",
    "        return max(left_edges * 2, 0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        deg = list(map(len,g))\n",
    "\n",
    "\n",
    "        left_edges = n-1\n",
    "\n",
    "        q=[]\n",
    "        for i,(d,c) in enumerate(zip(deg,coins)):\n",
    "            if d==1 and c==0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            left_edges -=1\n",
    "            for y in g[q.pop()]:\n",
    "                deg[y]-=1\n",
    "                if deg[y] ==1 and coins[y]==0:\n",
    "                    q.append(y)\n",
    "        \n",
    "        for i, (d,c) in enumerate(zip(deg,coins)):\n",
    "            if d==1 and c:\n",
    "                q.append(i)\n",
    "        left_edges -= len(q)\n",
    "        for x in q:\n",
    "            for y in g[x]:\n",
    "                deg[y] -=1\n",
    "                if deg[y] ==1:\n",
    "                    left_edges -=1\n",
    "        return max(left_edges*2,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        deg = list(map(len, g))\n",
    "\n",
    "        left_edges = n - 1\n",
    "        \n",
    "        q = []\n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "            if d == 1 and c == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            left_edges -= 1\n",
    "            for y in g[q.pop()]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1 and coins[y] == 0:\n",
    "                    q.append(y)\n",
    "        \n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "            if d == 1 and c:\n",
    "                q.append(i)\n",
    "        left_edges -= len(q)\n",
    "        for x in q:\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1:\n",
    "                    left_edges -= 1\n",
    "        return max(left_edges * 2, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        deg = list(map(len,g))\n",
    "\n",
    "\n",
    "        left_edges = n-1\n",
    "\n",
    "        q=[]\n",
    "        for i,(d,c) in enumerate(zip(deg,coins)):\n",
    "            if d==1 and c==0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            left_edges -=1\n",
    "            for y in g[q.pop()]:\n",
    "                deg[y]-=1\n",
    "                if deg[y] ==1 and coins[y]==0:\n",
    "                    q.append(y)\n",
    "        \n",
    "        for i, (d,c) in enumerate(zip(deg,coins)):\n",
    "            if d==1 and c:\n",
    "                q.append(i)\n",
    "        left_edges -= len(q)\n",
    "        for x in q:\n",
    "            for y in g[x]:\n",
    "                deg[y] -=1\n",
    "                if deg[y] ==1:\n",
    "                    left_edges -=1\n",
    "        return max(left_edges*2,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n=len(coins)\n",
    "        deg=[0]*n\n",
    "        graph=[[] for i in range(n)]\n",
    "        for i,j in edges:\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "            deg[i]+=1\n",
    "            deg[j]+=1\n",
    "        re_edges=n-1\n",
    "        q=[]\n",
    "        for i,(d,c) in enumerate(zip(deg,coins)):\n",
    "            if d==1 and c==0:\n",
    "                q.append(i)\n",
    "                re_edges-=1\n",
    "        while q:\n",
    "            for i in graph[q.pop()]:\n",
    "                deg[i]-=1\n",
    "                if deg[i]==1 and coins[i]==0:\n",
    "                    q.append(i)\n",
    "                    re_edges-=1\n",
    "        \n",
    "        for i,(d,c) in enumerate(zip(deg, coins)):\n",
    "            if d==1 and c:\n",
    "                q.append(i)\n",
    "                re_edges-=1\n",
    "        for x in q:\n",
    "            for y in graph[x]:\n",
    "                deg[y]-=1\n",
    "                if deg[y]==1:\n",
    "                    re_edges-=1\n",
    "        return max(0,re_edges*2) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "        deg = list(map(len, g))  # 每个节点的度数（邻居个数）\n",
    "\n",
    "        left_edges = n - 1  # 剩余边数\n",
    "        # 拓扑排序，去掉没有金币的子树\n",
    "        q = []\n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "            if d == 1 and c == 0:  # 没有金币的叶子\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            left_edges -= 1  # 删除节点到其父节点的边\n",
    "            node = q.pop()\n",
    "            deg[node] = 0\n",
    "            for y in g[node]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1 and coins[y] == 0:  # 没有金币的叶子\n",
    "                    q.append(y)\n",
    "\n",
    "        # 再次拓扑排序\n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "            if d == 1:  # 有金币的叶子（判断 c 是避免把没有金币的叶子也算进来）\n",
    "                q.append(i)\n",
    "        left_edges -= len(q)  # 删除所有叶子（到其父节点的边）\n",
    "        for x in q:  # 遍历所有叶子\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1:  # y 现在是叶子了\n",
    "                    left_edges -= 1  # 删除 y（到其父节点的边）\n",
    "        return max(left_edges * 2, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        # 关键点是要收集叶子结点的金币，叶子节点以内的金币是随着移动顺道就收集了\n",
    "        # 而后一种移动是必须的\n",
    "        n=len(edges)+1\n",
    "        tree=[[] for _ in range(n)]\n",
    "        degree=[0]*n\n",
    "        for i,j in edges:\n",
    "            tree[i].append(j)\n",
    "            tree[j].append(i)\n",
    "            degree[i]+=1\n",
    "            degree[j]+=1\n",
    "        \n",
    "        left_edges=n-1\n",
    "        q=deque()\n",
    "        for i in range(n):\n",
    "            if coins[i]==0 and degree[i]==1:\n",
    "                # degree[i]-=1\n",
    "                q.append(i) # 找到没有金币的叶节点，把他们去掉，不用考虑他们\n",
    "                left_edges-=1\n",
    "\n",
    "        while q:\n",
    "            x=q.popleft()\n",
    "            for j in tree[x]:\n",
    "                degree[j]-=1\n",
    "                if degree[j]==1 and coins[j]==0:\n",
    "                    degree[j]-=1\n",
    "                    q.append(j) # 用拓扑排序的方法删去不含金币的叶节点\n",
    "                    left_edges-=1\n",
    "        \n",
    "        # 接下来要删去所有包含金币的叶节点和这些节点的父节点，然后剩下的边就是所要走过的边\n",
    "        q=deque()\n",
    "        for i in range(n):\n",
    "            if coins[i]==1 and degree[i]==1:\n",
    "                degree[i]-=1\n",
    "                q.append(i) # 找到有金币的叶节点\n",
    "                left_edges-=1\n",
    "\n",
    "        for x in q:\n",
    "            for j in tree[x]:\n",
    "                degree[j]-=1\n",
    "                if degree[j]==1:\n",
    "                    left_edges-=1\n",
    "        \n",
    "        return max(2*left_edges,0) # 例如coins = [0,0], edges = [[0,1]],这个边就会被减掉两次\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [ [] for _ in range(n) ]\n",
    "        deg = [0] * n\n",
    "        for x,y in edges:\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if deg[i] == 1 and coins[i] == 0 :\n",
    "                q.append(i)\n",
    "        ans = n - 1\n",
    "        while q :\n",
    "            ans -= 1\n",
    "            for nxt in g[q.pop()]:\n",
    "                deg[nxt] -= 1\n",
    "                if coins[nxt] == 0 and deg[nxt] == 1:\n",
    "                    q.append(nxt)\n",
    "        for i in range(n):\n",
    "            if deg[i] == 1 and coins[i] == 1:\n",
    "                q.append(i)\n",
    "        while q : \n",
    "            ans -= 1\n",
    "            for nxt in g[q.pop()]:\n",
    "                deg[nxt] -= 1\n",
    "                if deg[nxt] == 1:\n",
    "                    ans -= 1\n",
    "        return max(0,ans ) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        d = [0]*n\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            d[a] += 1\n",
    "            d[b] += 1\n",
    "        q = list(filter(lambda i:d[i]==1 and coins[i]==0,range(n)))\n",
    "        while q:\n",
    "            x = q.pop()\n",
    "            d[x] = 0\n",
    "            for y in g[x]:\n",
    "                if d[y] == 0: continue\n",
    "                d[y] -= 1\n",
    "                if d[y] == 1 and coins[y] == 0:\n",
    "                    q.append(y)\n",
    "                break\n",
    "        q = list(filter(lambda i:d[i]==1,range(n)))\n",
    "        for _ in range(2):\n",
    "            new_q = []\n",
    "            for x in q:\n",
    "                d[x] = 0\n",
    "                for y in g[x]:\n",
    "                    if d[y] == 0: continue\n",
    "                    d[y] -= 1\n",
    "                    if d[y] == 1: new_q.append(y)\n",
    "                    break\n",
    "            q = new_q\n",
    "        return sum(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        degree = [0]*n\n",
    "        li = [[] for _ in range(n)]\n",
    "        for i,j in edges:\n",
    "            li[i].append(j)\n",
    "            li[j].append(i)\n",
    "            degree[i]+=1\n",
    "            degree[j]+=1\n",
    "            \n",
    "        v = [0]*n\n",
    "        q = deque([i for i,j in enumerate(degree) if j == 1])\n",
    "        temp = []\n",
    "        # def dfs(node):\n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            if coins[t] == 1:\n",
    "                temp.append(t)\n",
    "                continue\n",
    "            degree[t] = 0\n",
    "            v[t] = 1\n",
    "            for i in li[t]:\n",
    "                if v[i]:\n",
    "                    continue\n",
    "                degree[i] -= 1\n",
    "                if degree[i] == 1:\n",
    "                    q.append(i)\n",
    "        t2 = set()\n",
    "        for i in temp:\n",
    "            degree[i] = 0\n",
    "            v[i] = 1\n",
    "            for j in li[i]:\n",
    "                if v[j]:\n",
    "                    continue\n",
    "                degree[j] -= 1\n",
    "                if degree[j] == 1:\n",
    "                    v[j] = 1\n",
    "                    t2.add(j)\n",
    "                \n",
    "        for i in t2:\n",
    "            degree[i] = 0\n",
    "            for j in li[i]:\n",
    "                if not v[j]:\n",
    "                    degree[j] -= 1\n",
    "                    \n",
    "        return max(sum(degree),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        indegree = list(map(len, g))\n",
    "        q = []\n",
    "        for i, (d, c) in enumerate(zip(indegree, coins)):\n",
    "            if d == 1 and c == 0:\n",
    "                q.append(i)\n",
    "        ans = n - 1\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            ans -= 1\n",
    "            indegree[cur] -= 1\n",
    "            for neighbor in g[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 1 and coins[neighbor] == 0:\n",
    "                    q.append(neighbor)\n",
    "        # print(ans)\n",
    "        for idx, de in enumerate(indegree):\n",
    "            if de == 1 and coins[idx] == 1:\n",
    "                q.append(idx)\n",
    "        ans -= len(q)\n",
    "        # print(ans)\n",
    "        for item in q:\n",
    "            indegree[item] -= 1\n",
    "            for ne in g[item]:\n",
    "                indegree[ne] -= 1\n",
    "                if indegree[ne] == 1:\n",
    "                    ans -= 1\n",
    "        # print(ans)\n",
    "        return max(ans * 2, 0)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        e = [[] for _ in range(n)]\n",
    "        degree = [0]*n\n",
    "        for a,b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a) \n",
    "            degree[a]+=1\n",
    "            degree[b]+=1\n",
    "        \n",
    "        left_edges = n-1\n",
    "        # 删除所有不带金币的叶子节点\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if degree[i]==1 and coins[i]==0:\n",
    "                q.append(i)\n",
    "        while len(q):\n",
    "            v = q.popleft()\n",
    "            left_edges -= 1\n",
    "            for j in e[v]:\n",
    "                degree[j]-=1\n",
    "                if degree[j]==1 and coins[j]==0:\n",
    "                    q.append(j)\n",
    "        \n",
    "        # 删除所有带金币的叶子节点、这些节点的上一层节点\n",
    "        for i in range(n):\n",
    "            if degree[i]==1 and coins[i]==1:\n",
    "                q.append((i,0))\n",
    "        while len(q):\n",
    "            v,cnt = q.popleft()\n",
    "            left_edges -= 1\n",
    "            if cnt<1:\n",
    "                for j in e[v]:\n",
    "                    degree[j]-=1\n",
    "                    if degree[j]==1:\n",
    "                        q.append((j,cnt+1))\n",
    "        return max(left_edges*2,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "\n",
    "        # 用拓扑排序「剪枝」：去掉没有金币的子树\n",
    "        ss = set()\n",
    "        q = deque()\n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "            if d == 1 and c == 0:  # 无金币叶子\n",
    "                q.append(i)\n",
    "                ss.add(i)\n",
    "        while q:\n",
    "            for y in g[q.popleft()]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1 and coins[y] == 0:\n",
    "                    q.append(y)\n",
    "                    ss.add(y)\n",
    "\n",
    "        # 再次拓扑排序\n",
    "        for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "            if d == 1 and c:  # 有金币叶子\n",
    "                q.append(i)\n",
    "        if len(q) <= 1:  # 至多一个有金币的叶子，直接收集\n",
    "            return 0\n",
    "        time = [0] * n #有金币的走到i需要的步数。\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1:\n",
    "                    time[y] = time[x] + 1  # 记录入队时间 #度为1代表捡完所有金币才拣当前。有父亲，度肯定大于等于1\n",
    "                    q.append(y)\n",
    "        cnt = [0]*n\n",
    "        # 统计答案\n",
    "        for x,y in edges:\n",
    "            if x in ss or y in ss:continue\n",
    "            cnt[min(time[x],time[y])]+=1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            cnt[i]+=cnt[i+1]\n",
    "        return sum(time[x] >= 2 and time[y] >= 2 for x, y in edges) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        def remove_leafnode(check_fun):\n",
    "            que = deque()\n",
    "            for k, v in enumerate(neibours):\n",
    "                if v and len(v) == 1 and check_fun(k):\n",
    "                    que.append([k, v])\n",
    "                    neibours[k] = None\n",
    "            return que\n",
    "\n",
    "        def bfs_remove_leafnode(que, check_fun, max_loop):\n",
    "            idx = 0\n",
    "            while que and idx < max_loop:\n",
    "                idx += 1\n",
    "                k, v = que.popleft()\n",
    "                n_k, n_v = v[0], neibours[v[0]]\n",
    "                if n_v :\n",
    "                    n_v.remove(k)\n",
    "                    if len(n_v) == 1 and check_fun(n_k):\n",
    "                        que.append([n_k, n_v])\n",
    "                        neibours[n_k] = None\n",
    "\n",
    "        n = len(coins)\n",
    "        neibours = [[] for i in range(n)]\n",
    "        for p1, p2 in edges:\n",
    "            neibours[p1].append(p2)\n",
    "            neibours[p2].append(p1)\n",
    "        # print(neibours)\n",
    "\n",
    "        # remove empty leaf\n",
    "        que = remove_leafnode(lambda x: coins[x] == 0)\n",
    "        bfs_remove_leafnode(que, lambda x: coins[x] == 0, n)\n",
    "        # print(neibours)\n",
    "\n",
    "        # remove leaf with coin\n",
    "        que = remove_leafnode(lambda x: coins[x] == 1)\n",
    "        # print(neibours)\n",
    "\n",
    "        # remove leaf node whether contain coin or not\n",
    "        bfs_remove_leafnode(que, lambda x: True, len(que))\n",
    "        # print(neibours)\n",
    "\n",
    "        left_count = n - neibours.count(None)\n",
    "        return 0 if left_count == 0 else 2 * (left_count - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [[]  for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        print(g)\n",
    "        deg = list(map(len,g))\n",
    "        print(deg)\n",
    "        left_edges = n-1\n",
    "\n",
    "        q = []\n",
    "        for i,(d,c) in enumerate(zip(deg,coins)):\n",
    "            if d == 1 and c == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            left_edges -=1\n",
    "            t = q.pop()\n",
    "            for y in g[t]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1 and coins[y] == 0:\n",
    "                    q.append(y)\n",
    "        \n",
    "        for i,(d,c) in enumerate(zip(deg,coins)):\n",
    "            if d == 1 and c != 0:\n",
    "                q.append(i)\n",
    "        left_edges -= len(q)\n",
    "        for x in q:\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 1:\n",
    "                    left_edges -= 1\n",
    "\n",
    "        return max(left_edges*2,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        adjlist = {i:[] for i in range(n)}\n",
    "        degree = [0]*n\n",
    "        totals = n-1\n",
    "        for i, (a, b) in enumerate(edges):  #建图\n",
    "            adjlist[a].append(b)\n",
    "            adjlist[b].append(a)\n",
    "            degree[a] += 1\n",
    "            degree[b] += 1\n",
    "\n",
    "        q = [adjlist[i] for i in adjlist if coins[i]==0 and degree[i]==1] #无金币的叶节点\n",
    "        while q:    #循环去除无金币叶节点\n",
    "            totals -= 1\n",
    "            nodes = q.pop()\n",
    "            for x in nodes:\n",
    "                degree[x] -= 1\n",
    "                if degree[x] == 1 and coins[x] == 0:\n",
    "                    q.append(adjlist[x])\n",
    "        q = [adjlist[i] for i in adjlist if coins[i] and degree[i]==1] #有金币的叶节点\n",
    "        while q:    #循环去除有金币叶节点\n",
    "            totals -= 1\n",
    "            nodes = q.pop()\n",
    "            for x in nodes:\n",
    "                degree[x] -= 1\n",
    "                if degree[x] == 1:\n",
    "                    totals -= 1\n",
    "        return max(totals*2,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\r\n",
    "        import queue\r\n",
    "        ans = 0\r\n",
    "        n = len(coins)\r\n",
    "        edge_dict = {i: [] for i in range(n)}\r\n",
    "        degrees = [0 for _ in range(n)]\r\n",
    "        for edge in edges:\r\n",
    "            edge_dict[edge[0]].append(edge[1])\r\n",
    "            edge_dict[edge[1]].append(edge[0])\r\n",
    "        q = queue.Queue()\r\n",
    "        for i in range(n):\r\n",
    "            degrees[i] = len(edge_dict[i])\r\n",
    "            if coins[i] == 0 and degrees[i] == 1:\r\n",
    "                degrees[i] = 0\r\n",
    "                coins[i] = -1\r\n",
    "                q.put(i)\r\n",
    "        while not q.empty():\r\n",
    "            top = q.get()\r\n",
    "            for index in edge_dict[top]:\r\n",
    "                degrees[index] -= 1\r\n",
    "                if coins[index] == 0:\r\n",
    "                    if degrees[index] == 1:\r\n",
    "                        degrees[index] = 0\r\n",
    "                        coins[index] = -1\r\n",
    "                        q.put(index)\r\n",
    "        # print(coins)\r\n",
    "        # print(degrees)\r\n",
    "        q = queue.Queue()\r\n",
    "        step = 0\r\n",
    "        for i in range(n):\r\n",
    "            if coins[i] == 1 and degrees[i] == 1:\r\n",
    "                degrees[i] = 0\r\n",
    "                coins[i] = 0\r\n",
    "                q.put(i)\r\n",
    "        while not q.empty():\r\n",
    "            step += 1\r\n",
    "            temp_q = queue.Queue()\r\n",
    "            while not q.empty():\r\n",
    "                top = q.get()\r\n",
    "                for index in edge_dict[top]:\r\n",
    "                    degrees[index] -= 1\r\n",
    "                    if degrees[index] == 1:\r\n",
    "                        coins[index] = step\r\n",
    "                        temp_q.put(index)\r\n",
    "            q = temp_q\r\n",
    "        # print(coins)\r\n",
    "        # print(degrees)\r\n",
    "        for edge in edges:\r\n",
    "            if coins[edge[0]] >= 2 and coins[edge[1]] >= 2:\r\n",
    "                ans += 2\r\n",
    "        return int(ans)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\r\n",
    "        import queue\r\n",
    "        n = len(coins)\r\n",
    "        edge_dicts = {i:[]for i in range(n)}\r\n",
    "        for edge in edges:\r\n",
    "            edge_dicts[edge[0]].append(edge[1])\r\n",
    "            edge_dicts[edge[1]].append(edge[0])\r\n",
    "        degrees = [len(edge_dicts[i]) for i in range(n)]\r\n",
    "        q = queue.Queue()\r\n",
    "        for i in range(n):\r\n",
    "            if coins[i] == 0 and degrees[i] == 1:\r\n",
    "                q.put(i)\r\n",
    "                degrees[i] = 0\r\n",
    "                coins[i] = -1\r\n",
    "        while not q.empty():\r\n",
    "            temp_q = queue.Queue()\r\n",
    "            while not q.empty():\r\n",
    "                top = q.get()\r\n",
    "                for index in edge_dicts[top]:\r\n",
    "                    degrees[index] -= 1\r\n",
    "                    if coins[index] == 0 and degrees[index] == 1:\r\n",
    "                        temp_q.put(index)\r\n",
    "                        degrees[index] = 0\r\n",
    "                        coins[index] = -1\r\n",
    "            q = temp_q\r\n",
    "        for i in range(n):\r\n",
    "            if coins[i] == 1 and degrees[i] == 1:\r\n",
    "                q.put(i)\r\n",
    "                degrees[i] = 0\r\n",
    "                coins[i] = -1\r\n",
    "        for step in [-1,1]:\r\n",
    "            temp_q = queue.Queue()\r\n",
    "            while not q.empty():\r\n",
    "                top = q.get()\r\n",
    "                for index in edge_dicts[top]:\r\n",
    "                    degrees[index] -= 1\r\n",
    "                    if degrees[index] == 1:\r\n",
    "                        temp_q.put(index)\r\n",
    "                        degrees[index] = 0\r\n",
    "                        coins[index] = step\r\n",
    "            q = temp_q\r\n",
    "        ans = 0\r\n",
    "        for val in coins:\r\n",
    "            if val != -1:\r\n",
    "                ans += 1\r\n",
    "        return int(max(0,ans*2-2))\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = defaultdict(list)\n",
    "        degree = [0] * n\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "\n",
    "        rest=n\n",
    "        q=deque(i for i in range(n) if degree[i]==1 and coins[i]==0)\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            degree[u]-=1\n",
    "            rest-=1\n",
    "            for v in g[u]:\n",
    "                degree[v]-=1\n",
    "                if degree[v]==1 and coins[v]==0:\n",
    "                    q.append(v)\n",
    "        \n",
    "        for _ in range(2):\n",
    "            q=deque(i for i in range(n) if degree[i]==1)\n",
    "            while q:\n",
    "                u=q.popleft()\n",
    "                degree[u]-=1\n",
    "                rest-=1\n",
    "                for v in g[u]:\n",
    "                    degree[v]-=1\n",
    "        \n",
    "        return 0 if rest==0 else(rest-1)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        # cut zero leave\n",
    "        # cut leave round1\n",
    "        # cut leave round2\n",
    "        n = len(coins)\n",
    "        link = [0] * n\n",
    "        adj = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "            link[a] += 1\n",
    "            link[b] += 1\n",
    "        cutzero = []\n",
    "        for i in range(n):\n",
    "            if link[i] == 1 and coins[i] == 0:\n",
    "                link[i] = 0\n",
    "                b = adj[i][0]\n",
    "                adj[b].remove(i)\n",
    "                link[b] -= 1\n",
    "                cutzero.append(b)\n",
    "        while cutzero:\n",
    "            c = cutzero.pop()\n",
    "            if link[c] == 1 and coins[c] == 0:\n",
    "                link[c] = 0\n",
    "                b = adj[c][0]\n",
    "                adj[b].remove(c)\n",
    "                link[b] -= 1\n",
    "                cutzero.append(b)\n",
    "        # print(link)\n",
    "        for i in range(2):\n",
    "            cuts = []\n",
    "            for i in range(n):\n",
    "                if link[i] == 1:\n",
    "                    cuts.append(i)\n",
    "            for c in cuts:\n",
    "                link[c] = 0\n",
    "                for d in adj[c]:\n",
    "                    link[d]-=1\n",
    "                    adj[d].remove(c)\n",
    "        # print(link)\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            if link[i] != 0:\n",
    "                left += 1\n",
    "        if left <= 1:\n",
    "            return left\n",
    "        else:\n",
    "            return (left - 1) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = defaultdict(list)\n",
    "        degree = [0] * n\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        \n",
    "        rest = n\n",
    "        # 删除树中所有无金币的叶子节点，直到树中所有的叶子节点都是含有金币的\n",
    "        q = deque(i for i in range(n) if degree[i] == 1 and coins[i] == 0)\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            degree[u] -= 1\n",
    "            rest -= 1\n",
    "            for v in g[u]:\n",
    "                degree[v] -= 1\n",
    "                if degree[v] == 1 and coins[v] == 0:\n",
    "                    q.append(v)\n",
    "        \n",
    "        # 删除树中所有的叶子节点, 连续删除2次\n",
    "        for _ in range(2):\n",
    "            q = deque(i for i in range(n) if degree[i] == 1)\n",
    "            while q:\n",
    "                u = q.popleft()\n",
    "                degree[u] -= 1\n",
    "                rest -= 1\n",
    "                for v in g[u]:\n",
    "                    degree[v] -= 1\n",
    "        \n",
    "        return 0 if rest == 0 else (rest - 1) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        node_deps = {}\n",
    "        node_degrees = [0] * n\n",
    "        rest_node_count = n\n",
    "\n",
    "        # step1: 初始化树\n",
    "        for x, y in edges:\n",
    "            node_deps.setdefault(x, []).append(y)\n",
    "            node_degrees[x] += 1\n",
    "            node_deps.setdefault(y, []).append(x)\n",
    "            node_degrees[y] += 1\n",
    "\n",
    "        # step2: 删除所有无金币的叶子节点(度/degree=1, 且coin=0)\n",
    "        def remove_all_empty_coin_leaves():\n",
    "            nonlocal rest_node_count\n",
    "\n",
    "            def is_leaf_node(node_index):\n",
    "                return node_degrees[node_index] == 1 and coins[node_index] == 0\n",
    "\n",
    "            need_remove_nodes = deque(i for i in range(n) if is_leaf_node(i))\n",
    "            while need_remove_nodes:\n",
    "                # step2.1: 删除当前节点\n",
    "                crt_node = need_remove_nodes.popleft()\n",
    "                node_degrees[crt_node] -= 1\n",
    "                rest_node_count -= 1\n",
    "                # step2.2: 遍历并准备删除该节点对应的其他节点\n",
    "                for pair_node in node_deps[crt_node]:\n",
    "                    node_degrees[pair_node] -= 1\n",
    "                    if is_leaf_node(pair_node):\n",
    "                        need_remove_nodes.append(pair_node)\n",
    "\n",
    "        remove_all_empty_coin_leaves()\n",
    "\n",
    "        # step3: 删除树中的所有叶子节点, 并连续删除两次\n",
    "        def remove_all_leaves():\n",
    "            nonlocal rest_node_count\n",
    "\n",
    "            need_remove_nodes = deque(i for i in range(n) if node_degrees[i] == 1)\n",
    "            while need_remove_nodes:\n",
    "                crt_node = need_remove_nodes.popleft()\n",
    "                node_degrees[crt_node] -= 1\n",
    "                rest_node_count -= 1\n",
    "                for pair_node in node_deps[crt_node]:\n",
    "                    node_degrees[pair_node] -= 1\n",
    "\n",
    "        remove_all_leaves()\n",
    "        remove_all_leaves()\n",
    "\n",
    "        return 0 if rest_node_count <= 0 else (rest_node_count - 1) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        # 构建树\n",
    "        n=len(coins)\n",
    "        if n<=3:return 0\n",
    "        degree=[0]*n\n",
    "        g=defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            degree[u]+=1\n",
    "            degree[v]+=1\n",
    "        \n",
    "        res=n\n",
    "        # 删除没有金币的叶子节点\n",
    "        q=deque(i for i in range(n) if degree[i]==1 and coins[i]==0)\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            degree[u]-=1\n",
    "            res-=1\n",
    "            for v in g[u]:\n",
    "                degree[v]-=1\n",
    "                if degree[v]==1 and coins[v]==0:\n",
    "                    q.append(v)\n",
    "\n",
    "        # 删除包含金币的叶子节点\n",
    "        for _ in range(2):\n",
    "            q=deque(i for i in range(n) if degree[i]==1)\n",
    "            while q:\n",
    "                u=q.popleft()\n",
    "                degree[u]-=1\n",
    "                res-=1\n",
    "                for v in g[u]:\n",
    "                    if degree[v]>0:\n",
    "                        degree[v]-=1\n",
    "                        \n",
    "        return max((res-1)*2,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        graph = collections.defaultdict(list)\n",
    "        degree = [0] * n\n",
    "\n",
    "        rest = n\n",
    "\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            degree[edge[0]] += 1\n",
    "            degree[edge[1]] += 1\n",
    "\n",
    "        q = deque([i for i in range(n) if degree[i] == 1 and coins[i] == 0])\n",
    "\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            rest -= 1\n",
    "            degree[u] -= 1\n",
    "            for v in graph[u]:\n",
    "                degree[v] -= 1\n",
    "                if degree[v] == 1 and coins[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        for _ in range(2):\n",
    "            q = deque([i for i in range(n) if degree[i] == 1])\n",
    "            while q:\n",
    "                u = q.popleft()\n",
    "                degree[u] -= 1\n",
    "                rest -= 1\n",
    "                for v in graph[u]:\n",
    "                    degree[v] -= 1\n",
    "\n",
    "        return 0 if rest == 0 else 2 * (rest - 1)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = collections.defaultdict(list)\n",
    "        degree = [0] * n\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        \n",
    "        rest = n\n",
    "        # 叶子节点：degree = 1\n",
    "        # 删除树中所有无金币的叶子节点，直到树中所有的叶子节点都是含有金币的\n",
    "        q = collections.deque(i for i in range(n) if degree[i] == 1 and coins[i] == 0)\n",
    "        \n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            degree[u] -= 1\n",
    "            rest -= 1\n",
    "            for v in g[u]:\n",
    "                degree[v] -= 1\n",
    "                # 当删除了叶子节点，其所对应的父节点可能变成叶子节点，且没有coin，所有也需要删除\n",
    "                if degree[v] == 1 and coins[v] == 0:\n",
    "                    q.append(v)\n",
    "        \n",
    "        # 删除树中所有的叶子节点\n",
    "        for _ in range(2):\n",
    "            q = deque(i for i in range(n) if degree[i] == 1)\n",
    "            while q:\n",
    "                u = q.popleft()\n",
    "                degree[u] -= 1\n",
    "                rest -= 1\n",
    "                for v in g[u]:\n",
    "                    degree[v] -= 1\n",
    "        \n",
    "        return 0 if rest == 0 else (rest - 1) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(coins)\n",
    "        degree = [0] * n\n",
    "        edgeDict = defaultdict(list)\n",
    "\n",
    "        for x, y in edges:\n",
    "            edgeDict[x].append(y)\n",
    "            edgeDict[y].append(x)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        \n",
    "        # 删除无金币叶子节点\n",
    "        rest = n\n",
    "        q = [i for i in range(n) if degree[i] == 1 and coins[i] == 0]\n",
    "        while q:\n",
    "            u = q.pop()\n",
    "            degree[u] -= 1\n",
    "            rest -= 1\n",
    "            for v in edgeDict[u]:\n",
    "                degree[v] -= 1\n",
    "                if degree[v] == 1 and coins[v] == 0: q.append(v)\n",
    "\n",
    "        # 删除两次叶子\n",
    "        for _ in range(2):\n",
    "            q = deque(i for i in range(n) if degree[i] == 1)\n",
    "            while q:\n",
    "                u = q.popleft()\n",
    "                degree[u] -= 1\n",
    "                rest -= 1\n",
    "                for v in edgeDict[u]: degree[v] -= 1\n",
    "        \n",
    "        return 0 if rest == 0 else (rest - 1) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        # remove leaf nodes with the role: \n",
    "        # If a leaf node's coin is 0, remove it\n",
    "        # If a leaf node's coin is 1, remove it and set its neighbours' coins to max(2, coin)\n",
    "        # If a leaf node's coin is 2, moreve it and set its neighbours' coins to max(3, coin)\n",
    "        # n edges x2\n",
    "        n = len(coins)\n",
    "        node_edges = [[] for _ in coins]\n",
    "        for edge in edges:\n",
    "            node_edges[edge[0]] += [edge[1]]\n",
    "            node_edges[edge[1]] += [edge[0]]\n",
    "        \n",
    "        n_removed_nodes = 0\n",
    "        updated = True\n",
    "        while updated:\n",
    "            updated = False\n",
    "            for i in range(n):\n",
    "                if len(node_edges[i]) == 1 and coins[i] == 0: # is leaf node\n",
    "                    neighbour = node_edges[i][0]\n",
    "                    node_edges[neighbour].remove(i)\n",
    "                    node_edges[i] = []\n",
    "                    updated = True\n",
    "                    n_removed_nodes += 1\n",
    "        for _ in range(2):\n",
    "                node_edges_copy = [[e for e in node_edge] for node_edge in node_edges]\n",
    "                for i in range(n):\n",
    "                    if len(node_edges_copy[i]) == 1: # is leaf node\n",
    "                        if len(node_edges[i]) > 0:\n",
    "                            neighbour = node_edges[i][0]\n",
    "                            node_edges[neighbour].remove(i)\n",
    "                            node_edges[i] = []\n",
    "                            n_removed_nodes += 1\n",
    "\n",
    "        return (n-n_removed_nodes-1) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "\n",
    "        adj = [[] for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        for x, y in edges:\n",
    "            adj[x].append(y)\n",
    "            adj[y].append(x)\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        \n",
    "        queue = deque()\n",
    "        for i, val in enumerate(degree):\n",
    "            if val == 1 and coins[i] == 0:\n",
    "                queue.append(i)\n",
    "        \n",
    "        rm_nodes = set()\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            rm_nodes.add(cur)\n",
    "            for nxt in adj[cur]:\n",
    "                degree[nxt] -= 1\n",
    "                if degree[nxt] == 1 and coins[nxt] == 0:\n",
    "                    queue.append(nxt)\n",
    "        \n",
    "        for i, val in enumerate(degree):\n",
    "            if val == 1 and coins[i] > 0:\n",
    "                queue.append(i)\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            rm_nodes.add(cur)\n",
    "            for nxt in adj[cur]:\n",
    "                degree[nxt] -= 1\n",
    "                if degree[nxt] == 1:\n",
    "                    rm_nodes.add(nxt)\n",
    "            \n",
    "        return max(0, n - len(rm_nodes) - 1) * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        deg = collections.defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            deg[a] += 1\n",
    "            deg[b] += 1\n",
    "        n = len(coins)\n",
    "        q = collections.deque()\n",
    "        for i in range(n):\n",
    "            if deg[i] == 1 and coins[i] == 0:\n",
    "                deg[i] -= 1\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nx in g[cur]:\n",
    "                deg[nx] -= 1\n",
    "                if deg[nx] == 1 and coins[nx] == 0:\n",
    "                    q.append(nx)\n",
    "\n",
    "        q = collections.deque()\n",
    "        for i in range(n):\n",
    "            if deg[i] == 1 and coins[i]:\n",
    "                q.append(i)\n",
    "\n",
    "        time = [0]*n\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nx in g[cur]:\n",
    "                deg[nx] -= 1\n",
    "                if deg[nx] == 1:\n",
    "                    time[nx] = time[cur]+1\n",
    "                    q.append(nx)\n",
    "        ans = 0\n",
    "        for a, b in edges:\n",
    "            if time[a] >= 2 and time[b] >= 2:\n",
    "                ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(coins)\n",
    "        ct = [0]*n\n",
    "        ll = [[] for i in range(n)]\n",
    "        for item in edges:\n",
    "            ct[item[0]]+=1\n",
    "            ct[item[1]]+=1\n",
    "            ll[item[0]].append(item[1])\n",
    "            ll[item[1]].append(item[0])\n",
    "        \n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if coins[i]==0 and ct[i]==1:\n",
    "                q.append(i)\n",
    "\n",
    "        drop = set()\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            drop.add(cur)\n",
    "            ct[cur] = 0\n",
    "            for item in ll[cur]:\n",
    "                if item not in drop:\n",
    "                    ct[item]-=1\n",
    "                    if coins[item]==0 and ct[item]==1:\n",
    "                        q.append(item)\n",
    "        \n",
    "        q = []\n",
    "        q2 = []\n",
    "        for i in range(n):\n",
    "            if ct[i]==1:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            drop.add(cur)\n",
    "            for item in ll[cur]:\n",
    "                if item not in drop:\n",
    "                    ct[item]-=1\n",
    "                    if ct[item]==1:\n",
    "                        q2.append(item)\n",
    "        return max(2*(n-len(drop)-len(q2)-1), 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        degrees=[0 for _ in coins]\n",
    "        neib=[[] for __ in coins]\n",
    "        for x,y in edges:\n",
    "            degrees[x]+=1\n",
    "            degrees[y]+=1\n",
    "            neib[x].append(y)\n",
    "            neib[y].append(x)\n",
    "\n",
    "        # print(\"Edges\")\n",
    "        # for _ in neib:\n",
    "        #     print(_)\n",
    "        # print(\"Original\")\n",
    "        # print(coins)\n",
    "        # print(degrees)\n",
    "\n",
    "        # print(\"Leaves\")\n",
    "        leaves=[]\n",
    "        for i,(d,c) in enumerate(zip(degrees,coins)):\n",
    "            if d==1 and c==0:\n",
    "                leaves.append(i)\n",
    "        # print(leaves)\n",
    "        while leaves:\n",
    "            degrees[leaves[-1]]=0\n",
    "            for parentNode in neib[leaves.pop()]:\n",
    "                degrees[parentNode]-=1\n",
    "                if degrees[parentNode]==1 and coins[parentNode]==0:\n",
    "                    leaves.append(parentNode)\n",
    "            # print(leaves)\n",
    "\n",
    "        # print(\"Leaves removes\")\n",
    "        # print(coins)\n",
    "        # print(degrees)\n",
    "\n",
    "        layer1=[]\n",
    "        for i,d in enumerate(degrees):\n",
    "            if d==1:\n",
    "                degrees[i]=0\n",
    "                layer1.append(i)\n",
    "\n",
    "        for node in set(layer1):\n",
    "            for parentNode in neib[node]:\n",
    "                degrees[parentNode]-=1\n",
    "\n",
    "        # print(\"first layer removes\")\n",
    "        # print(coins)\n",
    "        # print(degrees)\n",
    "\n",
    "        layer2=[]\n",
    "        for i,d in enumerate(degrees):\n",
    "            if d==1:\n",
    "                degrees[i]=0\n",
    "                layer2.append(i)\n",
    "\n",
    "        for node in set(layer2):\n",
    "            for parentNode in neib[node]:\n",
    "                degrees[parentNode]-=1\n",
    "\n",
    "        # print(\"second layer removes\")\n",
    "        # print(coins)\n",
    "        # print(degrees)\n",
    "\n",
    "        answer=0\n",
    "        for deg in degrees:\n",
    "            if deg>0:\n",
    "                answer+=1\n",
    "\n",
    "        return max((answer-1) * 2, 0)\n",
    "\n",
    "\n",
    "        # def removeLeaves(coins,degrees,neib) -> int:\n",
    "        #     count=0\n",
    "        #     oldCoins=coins.copy()\n",
    "        #     oldDegrees=degrees.copy()\n",
    "        #     oldneib=neib.copy()\n",
    "        #     for i in range(len(coins)):\n",
    "        #         if oldCoins[i]==0 and oldDegrees[i]==1:\n",
    "        #             count+=1\n",
    "        #             if len(neib[i])==0:\n",
    "        #                 return -1\n",
    "        #             temp=list(neib[i])\n",
    "        #             j=temp[0]\n",
    "        #             degrees[i]=0\n",
    "        #             degrees[j]-=1\n",
    "        #             neib[j].remove(i)\n",
    "        #             neib[i].remove(j)\n",
    "        #             coins[i]=-1\n",
    "        #     return count\n",
    "        \n",
    "        # # Remove leaves without coins\n",
    "        # count=removeLeaves(coins,degrees,neib)\n",
    "        # while count>0:\n",
    "        #     count=removeLeaves(coins,degrees,neib)\n",
    "\n",
    "        # # Remove first layer\n",
    "        # zeros=[0 for coin in coins]\n",
    "        # removeLeaves(zeros,degrees,neib)\n",
    "        \n",
    "        # # Remove second layer\n",
    "        # zeros=[0 for coin in coins]\n",
    "        # removeLeaves(zeros,degrees,neib)\n",
    "\n",
    "        # answer=0\n",
    "        # for degree in degrees:\n",
    "        #     if degree!=0:\n",
    "        #         answer+=1\n",
    "        # return max(2*(answer-1),0)\n",
    "\n",
    "        # n = len(coins)\n",
    "        # g = [[] for _ in range(n)]\n",
    "        # for x, y in edges:\n",
    "        #     g[x].append(y)\n",
    "        #     g[y].append(x)  # 建图\n",
    "        # deg = list(map(len, g))  # 每个节点的度数（邻居个数）\n",
    "\n",
    "        # left_edges = n - 1  # 剩余边数\n",
    "        # # 拓扑排序，去掉没有金币的子树\n",
    "        # q = []\n",
    "        # for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "        #     if d == 1 and c == 0:  # 没有金币的叶子\n",
    "        #         q.append(i)\n",
    "        # while q:\n",
    "        #     left_edges -= 1  # 删除节点到其父节点的边\n",
    "        #     for y in g[q.pop()]:\n",
    "        #         deg[y] -= 1\n",
    "        #         if deg[y] == 1 and coins[y] == 0:  # 没有金币的叶子\n",
    "        #             q.append(y)\n",
    "\n",
    "        # # 再次拓扑排序\n",
    "        # for i, (d, c) in enumerate(zip(deg, coins)):\n",
    "        #     if d == 1 and c:  # 有金币的叶子（判断 c 是避免把没有金币的叶子也算进来）\n",
    "        #         q.append(i)\n",
    "        # left_edges -= len(q)  # 删除所有叶子（到其父节点的边）\n",
    "        # for x in q:  # 遍历所有叶子\n",
    "        #     for y in g[x]:\n",
    "        #         deg[y] -= 1\n",
    "        #         if deg[y] == 1:  # y 现在是叶子了\n",
    "        #             left_edges -= 1  # 删除 y（到其父节点的边）\n",
    "        # return max(left_edges * 2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        left_n = n\n",
    "        dic = {}\n",
    "        degree = [0] * n\n",
    "        for i,j in edges:\n",
    "            if i not in dic:\n",
    "                dic[i] = [j]\n",
    "            else:\n",
    "                dic[i].append(j)\n",
    "            if j not in dic:\n",
    "                dic[j] = [i]\n",
    "            else:\n",
    "                dic[j].append(i)   \n",
    "            degree[i] += 1\n",
    "            degree[j] += 1      \n",
    "        l = []\n",
    "        print(dic)\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1 and coins[i] == 0:\n",
    "                l.append(i)\n",
    "        while l:\n",
    "            node = l.pop(0)\n",
    "            left_n -= 1\n",
    "            degree[node] -= 1\n",
    "            print(dic[node])\n",
    "            \n",
    "            for node_neigbor in dic[node]:\n",
    "            #dic[node_neigbor].remove(node)\n",
    "                degree[node_neigbor] -= 1\n",
    "                if degree[node_neigbor] == 1 and coins[node_neigbor] == 0:\n",
    "                    l.append(node_neigbor)\n",
    "        \n",
    "        for j in range(2):\n",
    "            for i in range(n):\n",
    "                if degree[i] == 1:\n",
    "                    l.append(i)\n",
    "            while l:\n",
    "                node = l.pop()\n",
    "                left_n -= 1\n",
    "                degree[node] -= 1\n",
    "                for node_neigbor in dic[node]:\n",
    "                #dic[node_neigbor].remove(node)\n",
    "                    degree[node_neigbor] -= 1     \n",
    "\n",
    "        return 0 if left_n == 0 else 2*(left_n-1)           \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [[] for _ in range(n)]\n",
    "        d = [0] * n\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            d[x] += 1\n",
    "            d[y] += 1\n",
    "        \n",
    "        q = []\n",
    "        vis = set()\n",
    "        for index in range(n):\n",
    "            if d[index] == 1 and coins[index] == 0:\n",
    "                q.append(index)\n",
    "                vis.add(index)\n",
    "        \n",
    "        head, tail = 0, len(q)\n",
    "        while head < tail:\n",
    "            now = q[head]\n",
    "            head += 1\n",
    "            for nxt in g[now]:\n",
    "                d[nxt] -= 1\n",
    "                if d[nxt] == 1 and coins[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "                    vis.add(nxt)\n",
    "                    tail += 1\n",
    "        \n",
    "        q = []\n",
    "        f = [0] * n\n",
    "        for index in range(n):\n",
    "            if d[index] == 1 and coins[index] == 1:\n",
    "                q.append(index)\n",
    "                f[index] = 0\n",
    "                vis.add(index)\n",
    "        \n",
    "        head, tail = 0, len(q)\n",
    "        while head < tail:\n",
    "            now = q[head]\n",
    "            head += 1\n",
    "            for nxt in g[now]:\n",
    "                d[nxt] -= 1\n",
    "                if d[nxt] == 1 and nxt not in vis:\n",
    "                    f[nxt] = f[now] + 1\n",
    "                    q.append(nxt)\n",
    "                    tail += 1\n",
    "                    vis.add(nxt)\n",
    "        \n",
    "        res = 0\n",
    "        for x, y in edges:\n",
    "            if f[x] >= 2 and f[y] >= 2:\n",
    "                res += 2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        g = [set() for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        for i in range(n):\n",
    "            coins[i] *= 3\n",
    "        for i in range(n):\n",
    "            # leave\n",
    "            if len(g[i]) == 1:\n",
    "                # print(i, coins)\n",
    "                cur = i\n",
    "                while coins[cur] == 0 and len(g[cur]) == 1:\n",
    "                    # print(i, coins)\n",
    "                    # print()\n",
    "                    (newCur, ) = g[cur]\n",
    "                    g[cur].remove(newCur)\n",
    "                    g[newCur].remove(cur)\n",
    "                    cur = newCur\n",
    "                if len(g[cur]) != 1:\n",
    "                    continue    \n",
    "                while coins[cur] != 1 and len(g[cur]) == 1:\n",
    "                    (newCur, ) = g[cur]\n",
    "                    g[cur].remove(newCur)\n",
    "                    g[newCur].remove(cur)\n",
    "                    if coins[newCur] != 0:\n",
    "                        coins[newCur] = min(coins[newCur], coins[cur] - 1)\n",
    "                    else:\n",
    "                        coins[newCur] = coins[cur] - 1\n",
    "                    coins[cur] = 0\n",
    "                    cur = newCur\n",
    "                    \n",
    "        # print(coins)\n",
    "        # print(g)\n",
    "        res = 0\n",
    "        for e in g:\n",
    "            res += len(e)\n",
    "        \n",
    "        return res\n",
    "                \n",
    "                    \n",
    "                    \n",
    "                    \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        ind = collections.Counter()\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            ind[a] += 1 \n",
    "            ind[b] += 1 \n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        queue = collections.deque([node for node in ind if ind[node] == 1 and coins[node] == 0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                ind[nei] -= 1 \n",
    "                if ind[nei] == 1 and coins[nei] == 0:\n",
    "                    queue.append(nei)\n",
    "            ind[cur] = 0\n",
    "        for _ in range(2):\n",
    "            queue = [node for node in ind if ind[node] == 1]\n",
    "            for cur in queue:\n",
    "                for nei in graph[cur]:\n",
    "                    ind[nei] -= 1 \n",
    "                ind[cur] = 0\n",
    "        return (max(sum(ind[node] > 0 for node in range(n)), 1) - 1) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        N = len(coins)\n",
    "        \n",
    "        dist = defaultdict(int)\n",
    "        neighber = defaultdict(list)\n",
    "        p = [0] * N\n",
    "\n",
    "        for a, b in edges:\n",
    "            neighber[a].append(b)\n",
    "            neighber[b].append(a)\n",
    "            p[a] += 1\n",
    "            p[b] += 1\n",
    "\n",
    "        q = deque()\n",
    "        for i in range(N):\n",
    "            if p[i]==1 and coins[i]==0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            a = q.popleft()\n",
    "            p[a] -= 1\n",
    "            for b in neighber[a]:\n",
    "                p[b] -= 1\n",
    "                if p[b] == 1 and coins[b]==0:\n",
    "                    q.append(b)\n",
    "        for i in range(N):\n",
    "            if p[i] == 1:\n",
    "                q.append(i)\n",
    "        for _ in range(2):\n",
    "            for _ in range(len(q)):\n",
    "                a = q.popleft()\n",
    "                if p[a] == 0:\n",
    "                    continue\n",
    "                p[a] -= 1\n",
    "                for b in neighber[a]:\n",
    "                    if p[b] == 0:\n",
    "                        continue\n",
    "                    p[b] -= 1\n",
    "                    if p[b] == 1:\n",
    "                        q.append(b)\n",
    "                        coins[b] += coins[a]\n",
    "        if not q:\n",
    "            return 0\n",
    "        last = 0\n",
    "        while q:\n",
    "            a = q.popleft()\n",
    "            last = a\n",
    "            if p[a] == 0:\n",
    "                continue\n",
    "            p[a] -= 1\n",
    "            assert p[a] == 0\n",
    "            d = sum([dist[(a,i)] for i in neighber[a]])\n",
    "            for b in neighber[a]:\n",
    "                if p[b] == 0:\n",
    "                    continue\n",
    "                p[b] -= 1\n",
    "                if p[b] == 1:\n",
    "                    q.append(b)\n",
    "                if coins[a] > 0:\n",
    "                    dist[(b,a)] = d+1\n",
    "                    coins[b] += coins[a]\n",
    "        return sum([dist[(last,i)] for i in neighber[last]]) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        graph = defaultdict(list)\n",
    "        degree = [0 for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "            degree[a] += 1\n",
    "            degree[b] += 1\n",
    "        \n",
    "        q = deque()\n",
    "        q1 = deque()\n",
    "        for i, d in enumerate(degree):\n",
    "            if d == 1:\n",
    "                if coins[i] == 0:\n",
    "                    q.append(i)\n",
    "        total_edges = n - 1\n",
    "        \n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            total_edges -= 1\n",
    "            for nei in graph[node]:\n",
    "                if degree[nei] == 0:\n",
    "                    continue\n",
    "                degree[nei] -= 1\n",
    "                if degree[nei] == 1 and coins[nei] == 0:\n",
    "                    q.append(nei)\n",
    "        for i, d in enumerate(degree):\n",
    "            if d == 1:\n",
    "                if coins[i] == 1:\n",
    "                    q1.append([i, 0])\n",
    "        while q1:\n",
    "            node, dist = q1.popleft()\n",
    "            if dist == 2:\n",
    "                continue\n",
    "            total_edges -= 1\n",
    "            for nei in graph[node]:\n",
    "                degree[nei] -= 1\n",
    "                if degree[nei] == 1:\n",
    "                    q1.append([nei, dist + 1])\n",
    "        return max(total_edges * 2, 0)\n",
    "\n",
    "                \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        def save_relation(x, y):\n",
    "            if x in neibours:\n",
    "                neibours[x].append(y)\n",
    "            else:\n",
    "                neibours[x] = [y]\n",
    "\n",
    "        def remove_leafnode(check_fun):\n",
    "            que = deque()\n",
    "            lt = [it for it in neibours.items()]\n",
    "            for k, v in lt:\n",
    "                if len(v) == 1 and check_fun(k):\n",
    "                    que.append([k, v])\n",
    "                    del neibours[k]\n",
    "            return que\n",
    "\n",
    "        def bfs_remove_leafnode(que, check_fun, max_loop):\n",
    "            idx = 0\n",
    "            while que and idx < max_loop:\n",
    "                k, v = que.popleft()\n",
    "                if v[0] not in neibours:\n",
    "                    continue\n",
    "                n_k, n_v = v[0], neibours[v[0]]\n",
    "                n_v.remove(k)\n",
    "                idx += 1\n",
    "                if len(n_v) == 1 and check_fun(n_k):\n",
    "                    que.append([n_k, n_v])\n",
    "                    del neibours[n_k]\n",
    "\n",
    "        neibours = {}\n",
    "        for p1, p2 in edges:\n",
    "            save_relation(p1, p2)\n",
    "            save_relation(p2, p1)\n",
    "\n",
    "        # remove empty leaf\n",
    "        que = remove_leafnode(lambda x: coins[x] == 0)\n",
    "        bfs_remove_leafnode(que, lambda x: coins[x] == 0, len(coins))\n",
    "        # print(neibours)\n",
    "\n",
    "        # remove leaf with coin\n",
    "        que = remove_leafnode(lambda x: coins[x] == 1)\n",
    "        # print(neibours)\n",
    "\n",
    "        # remove leaf node whether contain coin or not\n",
    "        bfs_remove_leafnode(que, lambda x: True, len(que))\n",
    "        # print(neibours)\n",
    "\n",
    "        return 0 if len(neibours) == 0 else 2 * (len(neibours) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        if sum(coins) <= 1: return 0\n",
    "        G = [set() for i in range(n)]\n",
    "        for i,j in edges:\n",
    "            G[i].add(j)\n",
    "            G[j].add(i)\n",
    "\n",
    "        topo = [i for i in range(n) if len(G[i]) == 1 and coins[i] == 0]\n",
    "        for i in topo:\n",
    "            j = list(G[i])[0]\n",
    "            G[j].remove(i)\n",
    "            G[i].remove(j)\n",
    "            if coins[j] == 0 and len(G[j]) == 1:\n",
    "                topo.append(j)\n",
    "\n",
    "        for _ in range(2):\n",
    "            topo = [i for i in range(n) if len(G[i]) == 1]\n",
    "            for i in topo:\n",
    "                if G[i]:\n",
    "                    j = list(G[i])[0]\n",
    "                    G[j].remove(i)\n",
    "                    G[i].remove(j)\n",
    "        x = sum(len(G[i]) > 0 for i in range(n))\n",
    "        return max(x - 1, 0) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        ind = collections.Counter()\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "            ind[a] += 1 \n",
    "            ind[b] += 1 \n",
    "        queue = collections.deque([node for node in range(n) if ind[node] == 1 and coins[node] == 0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                ind[nei] -= 1 \n",
    "                if ind[nei] == 1 and coins[nei] == 0:\n",
    "                    queue.append(nei)\n",
    "            ind[cur] = 0\n",
    "        for _ in range(2):\n",
    "            queue = collections.deque([node for node in range(n) if ind[node] == 1])\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                for nei in graph[cur]:\n",
    "                    ind[nei] -= 1 \n",
    "                ind[cur] = 0\n",
    "        return (max(sum(ind[node] > 0 for node in range(n)), 1) - 1) * 2\n",
    "\n",
    "\n",
    "        n = len(coins)\n",
    "        ind = collections.Counter()\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            ind[a] += 1 \n",
    "            ind[b] += 1 \n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        queue = collections.deque([node for node in ind if ind[node] == 1 and coins[node] == 0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                ind[nei] -= 1 \n",
    "                if ind[nei] == 1 and coins[nei] == 0:\n",
    "                    queue.append(nei)\n",
    "            ind[cur] = 0\n",
    "        for _ in range(2):\n",
    "            queue = [node for node in ind if ind[node] == 1]\n",
    "            for cur in queue:\n",
    "                for nei in graph[cur]:\n",
    "                    ind[nei] -= 1 \n",
    "                ind[cur] = 0\n",
    "        return (max(sum(ind[node] > 0 for node in range(n)), 1) - 1) * 2\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        degree = Counter()\n",
    "        for src, dst in edges:\n",
    "            graph[src].append(dst)\n",
    "            graph[dst].append(src)\n",
    "            degree[src], degree[dst] = degree[src] + 1, degree[dst] + 1\n",
    "        \n",
    "        rest, stack = len(coins), []\n",
    "        for key in graph.keys():\n",
    "            if degree[key] == 1 and coins[key] == 0:\n",
    "                stack.append(key)\n",
    "                rest -= 1\n",
    "        while len(stack):\n",
    "            node = stack.pop()\n",
    "            for adj in graph[node]:\n",
    "                degree[adj] -= 1\n",
    "                degree[node] -= 1\n",
    "                if degree[adj] == 1 and coins[adj] == 0:\n",
    "                    stack.append(adj)\n",
    "                    rest -= 1\n",
    "        \n",
    "        for _ in range(2):\n",
    "            for key in graph.keys():\n",
    "                if degree[key] == 1:\n",
    "                    stack.append(key)\n",
    "                    rest -= 1\n",
    "            while len(stack):\n",
    "                node = stack.pop()\n",
    "                for adj in graph[node]:\n",
    "                    degree[node] -= 1\n",
    "                    degree[adj] -= 1\n",
    "        \n",
    "        return 0 if rest == 0 else 2*(rest - 1)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        ind = collections.Counter()\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "            ind[a] += 1 \n",
    "            ind[b] += 1 \n",
    "        queue = collections.deque([node for node in range(n) if ind[node] == 1 and coins[node] == 0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                ind[nei] -= 1 \n",
    "                if ind[nei] == 1 and coins[nei] == 0:\n",
    "                    queue.append(nei)\n",
    "            ind[cur] = 0\n",
    "        for _ in range(2):\n",
    "            queue = collections.deque([node for node in range(n) if ind[node] == 1])\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                for nei in graph[cur]:\n",
    "                    ind[nei] -= 1 \n",
    "                ind[cur] = 0\n",
    "        return (max(sum(ind[node] > 0 for node in range(n)), 1) - 1) * 2\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        ind = collections.Counter()\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "            ind[a] += 1 \n",
    "            ind[b] += 1 \n",
    "        queue = collections.deque([node for node in range(n) if ind[node] == 1 and coins[node] == 0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                ind[nei] -= 1 \n",
    "                if ind[nei] == 1 and coins[nei] == 0:\n",
    "                    queue.append(nei)\n",
    "            ind[cur] = - 1 \n",
    "        for _ in range(2):\n",
    "            queue = collections.deque([node for node in range(n) if ind[node] == 1])\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                for nei in graph[cur]:\n",
    "                    ind[nei] -= 1 \n",
    "                ind[cur] = - 1\n",
    "        return (max(sum(ind[node] > 0 for node in range(n)), 1) - 1) * 2\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        ind = collections.Counter()\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "            ind[a] += 1 \n",
    "            ind[b] += 1 \n",
    "        queue = collections.deque([node for node in range(n) if ind[node] == 1 and coins[node] == 0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                ind[nei] -= 1 \n",
    "                if ind[nei] == 1 and coins[nei] == 0:\n",
    "                    queue.append(nei)\n",
    "            ind[cur] = 0\n",
    "        for _ in range(2):\n",
    "            queue = collections.deque([node for node in range(n) if ind[node] == 1])\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                for nei in graph[cur]:\n",
    "                    ind[nei] -= 1 \n",
    "                ind[cur] = 0\n",
    "        return (max(sum(ind[node] > 0 for node in range(n)), 1) - 1) * 2\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        edgeDict = {i:[] for i in range(n)}\n",
    "        for edge in edges:\n",
    "            edgeDict[edge[0]].append(edge[1])\n",
    "            edgeDict[edge[1]].append(edge[0])\n",
    "        left_edge = n - 1\n",
    "        degree = {}\n",
    "        # deg = list(map(len, g))\n",
    "        for i in range(n):\n",
    "            degree[i] = len(edgeDict[i])\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1 and coins[i] == 0:\n",
    "                q.append(i)\n",
    "        print(degree)\n",
    "        print(q)\n",
    "        while q:\n",
    "            left_edge -= 1\n",
    "            for node in edgeDict[q.pop()]:\n",
    "                degree[node] -= 1\n",
    "                if degree[node] == 1 and coins[node] == 0:\n",
    "                    q.append(node)\n",
    "        print(q)\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1 and coins[i] == 1:\n",
    "                q.append(i)\n",
    "        print(q)\n",
    "        left_edge = left_edge - len(q)\n",
    "        # print(left_edge)\n",
    "        for node in q:\n",
    "            for fa in edgeDict[node]:\n",
    "                degree[fa] -= 1\n",
    "                if degree[fa] == 1:\n",
    "                    left_edge -= 1\n",
    "        \n",
    "        return max(left_edge*2,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MAX_DISTANCE = 2\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        degrees = [0] * n\n",
    "        adjacencyList = [set() for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            degrees[a] += 1\n",
    "            degrees[b] += 1\n",
    "            adjacencyList[a].add(b)\n",
    "            adjacencyList[b].add(a)\n",
    "\n",
    "        # cut useless\n",
    "        for i in range(n):\n",
    "            a = i\n",
    "            while degrees[a] == 1 and coins[a] == 0:\n",
    "                b = adjacencyList[a].pop()\n",
    "                adjacencyList[b].remove(a)\n",
    "                degrees[a] -= 1\n",
    "                degrees[b] -= 1\n",
    "                a = b\n",
    "\n",
    "        # collect coins\n",
    "        for i in range(n):\n",
    "            if degrees[i] != 1:\n",
    "                continue\n",
    "            a = i\n",
    "            for j in range(Solution.MAX_DISTANCE):\n",
    "                if degrees[a] != 1 or coins[a] == None:\n",
    "                    break\n",
    "                b = adjacencyList[a].pop()\n",
    "                adjacencyList[b].remove(a)\n",
    "                degrees[a] -= 1\n",
    "                degrees[b] -= 1\n",
    "                a = b\n",
    "            else:\n",
    "                coins[a] = None\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += degrees[i]\n",
    "        return ans    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins, edges) -> int:\n",
    "        deleted = set()\n",
    "        l = len(coins)\n",
    "        input_degree = [0] * l \n",
    "        connections = {}\n",
    "        for start,end in edges:\n",
    "            input_degree[start]+=1\n",
    "            input_degree[end]+=1\n",
    "            if start not in connections:connections[start]=[]\n",
    "            connections[start].append(end)\n",
    "            if end not in connections:connections[end]=[]\n",
    "            connections[end].append(start)\n",
    "        leaves = []\n",
    "        leaves_with_coin = []\n",
    "        for i in range(l):\n",
    "            if input_degree[i]==1 :\n",
    "                if coins[i]==0:\n",
    "                    deleted.add(i)\n",
    "                    leaves.append(i)\n",
    "                else:\n",
    "                    leaves_with_coin.append(i)\n",
    "        while leaves:\n",
    "            tmp = []\n",
    "            for ll in leaves:\n",
    "                cons = connections[ll]\n",
    "                for con in cons:\n",
    "                    if con in deleted:continue\n",
    "                    input_degree[con]-=1\n",
    "                    if input_degree[con]==1 :\n",
    "                        if coins[con]==0:\n",
    "                            tmp.append(con)\n",
    "                            deleted.add(con)\n",
    "                        else:\n",
    "                            leaves_with_coin.append(con)\n",
    "            leaves = tmp\n",
    "        for ll in leaves_with_coin:\n",
    "            deleted.add(ll)\n",
    "            cons = connections[ll]\n",
    "            for con in cons:\n",
    "                if con in deleted:continue\n",
    "                input_degree[con]-=1\n",
    "                if input_degree[con]==1:\n",
    "                    deleted.add(con)\n",
    "        res = 0\n",
    "        for start,end in edges:\n",
    "            if start not in deleted and end not in deleted:res += 1\n",
    "\n",
    "        return res * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        tree = [set() for _ in range(n)]\n",
    "        \n",
    "        # Build the tree from the edges\n",
    "        for e in edges:\n",
    "            tree[e[0]].add(e[1])\n",
    "            tree[e[1]].add(e[0])\n",
    "        \n",
    "        # Find the leaves with zero coins\n",
    "        leaf = []\n",
    "        for i in range(n):\n",
    "            u = i\n",
    "            while len(tree[u]) == 1 and coins[u] == 0:\n",
    "                v = tree[u].pop()\n",
    "                tree[v].remove(u)\n",
    "                u = v\n",
    "            if len(tree[u]) == 1:\n",
    "                leaf.append(u)\n",
    "        \n",
    "        # Remove the leaves one by one\n",
    "        for sz in range(2, 0, -1):\n",
    "            temp = []\n",
    "            for u in leaf:\n",
    "                if len(tree[u]) == 1:\n",
    "                    v = tree[u].pop()\n",
    "                    tree[v].remove(u)\n",
    "                    if len(tree[v]) == 1:\n",
    "                        temp.append(v)\n",
    "            leaf = temp\n",
    "        \n",
    "        # Count the remaining edges in the tree\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += len(tree[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connNet(self,edges,coins):\n",
    "        net = [[] for _ in range(len(coins))]\n",
    "        netlen = [0] * len(coins)\n",
    "        #print('\\n--------\\nconis:',coins,'\\nedges:',edges)\n",
    "        for edge in edges:\n",
    "            net[edge[0]] += [edge[1]]\n",
    "            net[edge[1]] += [edge[0]]\n",
    "            netlen[edge[0]] += 1\n",
    "            netlen[edge[1]] += 1\n",
    "        #print('net:', net, \"\\nlen:\", netlen)\n",
    "\n",
    "        for i,conns in enumerate(net):\n",
    "            leaf = i\n",
    "            #print('leaf:', leaf, 'len:', netlen[leaf], 'coin:', coins[leaf])\n",
    "            while(netlen[leaf] == 1 and coins[leaf] == 0): \n",
    "                #print('del leaf:', leaf,'len:',netlen[leaf],'coin:', coins[leaf])\n",
    "                netlen[leaf] = 0\n",
    "                delleaf = leaf\n",
    "                leaf = net[delleaf][0]\n",
    "                #print('n-leaf:', leaf,'len:', netlen[leaf], 'from net:',net[leaf],'del ',delleaf)\n",
    "                netlen[leaf] -= 1\n",
    "                net[leaf].remove(delleaf)\n",
    "\n",
    "        netlen2 = netlen.copy()\n",
    "        for _ in range(2):\n",
    "            if _ == 1:\n",
    "                netlen = netlen2.copy()\n",
    "            for i,conns in enumerate(net):\n",
    "                if(netlen[i] == 1): \n",
    "                    #print('del level ',_, 'leaf:', i, 'len:', netlen[i])\n",
    "                    netlen[i] = 0\n",
    "                    netlen2[i] = 0\n",
    "                    leaf = conns[0]\n",
    "                    netlen2[leaf] -= 1\n",
    "                    #print('father:', leaf, netlen[leaf])\n",
    "                    #net[leaf].remove(i)            \n",
    "        \n",
    "        return(max(0, 2*(len(coins)-netlen.count(0)-1)))\n",
    "\n",
    "    def collectTheCoins1(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        net = [[] for _ in range(len(coins))]\n",
    "        netlen = [0] * len(coins)\n",
    "        for edge in edges:\n",
    "            net[edge[0]] += [edge[1]]\n",
    "            net[edge[1]] += [edge[0]]\n",
    "            netlen[edge[0]] += 1\n",
    "            netlen[edge[1]] += 1\n",
    "        for i,conns in enumerate(net):\n",
    "            leaf = i\n",
    "            while(netlen[leaf] == 1 and coins[leaf] == 0): \n",
    "                netlen[leaf] = 0\n",
    "                delleaf = leaf\n",
    "                leaf = net[delleaf][0]\n",
    "                netlen[leaf] -= 1\n",
    "                net[leaf].remove(delleaf)\n",
    "\n",
    "        netlen2 = netlen.copy()\n",
    "        for _ in range(2):\n",
    "            if _ == 1:\n",
    "                netlen = netlen2.copy()\n",
    "            for i,conns in enumerate(net):\n",
    "                if(netlen[i] == 1): \n",
    "                    netlen[i] = 0\n",
    "                    netlen2[i] = 0\n",
    "                    leaf = conns[0]\n",
    "                    netlen2[leaf] -= 1\n",
    "        \n",
    "        return(max(0, 2*(len(coins)-netlen.count(0)-1)))\n",
    "\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        net = [set() for _ in range(len(coins))]\n",
    "        netlen = [0] * len(coins)\n",
    "        for edge in edges:\n",
    "            net[edge[0]].add(edge[1])\n",
    "            net[edge[1]].add(edge[0])\n",
    "            netlen[edge[0]] += 1\n",
    "            netlen[edge[1]] += 1\n",
    "        for i,conns in enumerate(net):\n",
    "            leaf = i\n",
    "            while(netlen[leaf] == 1 and coins[leaf] == 0): \n",
    "                netlen[leaf] = 0\n",
    "                delleaf = leaf\n",
    "                leaf = net[delleaf].pop()\n",
    "                netlen[leaf] -= 1\n",
    "                net[leaf].discard(delleaf)\n",
    "\n",
    "        netlen2 = netlen.copy()\n",
    "        for _ in range(2):\n",
    "            if _ == 1:\n",
    "                netlen = netlen2.copy()\n",
    "            for i,conns in enumerate(net):\n",
    "                if(netlen[i] == 1): \n",
    "                    netlen[i] = 0\n",
    "                    netlen2[i] = 0\n",
    "                    leaf = conns.pop()\n",
    "                    netlen2[leaf] -= 1\n",
    "        \n",
    "        return(max(0, 2*(len(coins)-netlen.count(0)-1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        G = [set() for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            G[a].add(b)\n",
    "            G[b].add(a)\n",
    "        \n",
    "        q = deque(i for i in range(n) if len(G[i]) == 1 and coins[i] == 0)\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            j = G[i].pop()\n",
    "            G[j].remove(i)\n",
    "            if len(G[j]) == 0:\n",
    "                return 0\n",
    "            if len(G[j]) == 1 and coins[j] == 0:\n",
    "                q.append(j)\n",
    "\n",
    "        for _ in range(2):\n",
    "            q = [i for i in range(n) if len(G[i]) == 1]\n",
    "            for i in q:\n",
    "                if not G[i]: continue\n",
    "                j = G[i].pop()\n",
    "                G[j].remove(i)\n",
    "\n",
    "        e = sum(len(G[i]) > 0 for i in range(n))\n",
    "        return 2 * max(0, e-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        e = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        directed = [-1] * len(coins)\n",
    "        def find_farthest_coin(node, num_coin):\n",
    "            vis = {node}\n",
    "            cur = {node}\n",
    "            dist = 0\n",
    "            ret = node\n",
    "            num_coin -= coins[node]\n",
    "            while num_coin > 0:\n",
    "                nxt = set()\n",
    "                dist += 1\n",
    "                for x in cur:\n",
    "                    for y in e[x]:\n",
    "                        if y not in vis:\n",
    "                            nxt.add(y)\n",
    "                            directed[y] = x\n",
    "                            if coins[y]:\n",
    "                                ret = y\n",
    "                                num_coin -= 1\n",
    "                vis |= nxt\n",
    "                cur = nxt\n",
    "            return ret, dist\n",
    "        n = sum(coins)\n",
    "        if n < 2: return 0\n",
    "        foo, bar = find_farthest_coin(0, n)\n",
    "        bar, l = find_farthest_coin(foo, n)\n",
    "        if l <= 4: return 0\n",
    "        center = directed[directed[bar]]\n",
    "        find_farthest_coin(center, n)\n",
    "        subtree = {center}\n",
    "        for i in range(len(coins)):\n",
    "            if coins[i]:\n",
    "                cur = directed[directed[i]]\n",
    "                while cur not in subtree:\n",
    "                    subtree.add(cur)\n",
    "                    cur = directed[cur]\n",
    "        # print(subtree)\n",
    "        return len(subtree) * 2 - 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        tree = [set() for _ in range(n)]\n",
    "        \n",
    "        # Build the tree from the edges\n",
    "        for e in edges:\n",
    "            tree[e[0]].add(e[1])\n",
    "            tree[e[1]].add(e[0])\n",
    "        \n",
    "        # Find the leaves with zero coins\n",
    "        leaf = []\n",
    "        for i in range(n):\n",
    "            u = i\n",
    "            while len(tree[u]) == 1 and coins[u] == 0:\n",
    "                v = tree[u].pop()\n",
    "                tree[v].remove(u)\n",
    "                u = v\n",
    "            if len(tree[u]) == 1:\n",
    "                leaf.append(u)\n",
    "        \n",
    "        # Remove the leaves one by one\n",
    "        for sz in range(2, 0, -1):\n",
    "            temp = []\n",
    "            for u in leaf:\n",
    "                if len(tree[u]) == 1:\n",
    "                    v = tree[u].pop()\n",
    "                    tree[v].remove(u)\n",
    "                    if len(tree[v]) == 1:\n",
    "                        temp.append(v)\n",
    "            leaf = temp\n",
    "        \n",
    "        # Count the remaining edges in the tree\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += len(tree[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        trees = [set() for i in range(n)]\n",
    "        for edge in edges:\n",
    "            trees[edge[0]].add(edge[1])\n",
    "            trees[edge[1]].add(edge[0])\n",
    "        q = deque(i for i in range(n) if len(trees[i])==1 and coins[i]==0)\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            for sibling in trees[node]:\n",
    "                trees[sibling].remove(node)\n",
    "                if len(trees[sibling]) == 1 and coins[sibling] == 0:\n",
    "                    q.append(sibling)\n",
    "            trees[node] = set()\n",
    "        # 摘掉叶节点\n",
    "        for _ in range(2):\n",
    "            need_remove = [i for i in range(n) if len(trees[i]) == 1]\n",
    "            for rm in need_remove:\n",
    "                for sibling in trees[rm]:\n",
    "                    trees[sibling].remove(rm)\n",
    "                trees[rm] = set()\n",
    "\n",
    "        res_node = 0\n",
    "        for i in range(n):\n",
    "            if len(trees[i]) > 0:\n",
    "                res_node += 1\n",
    "        if res_node < 2:\n",
    "            return 0\n",
    "        return 2*(res_node-1)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, c: List[int], e: List[List[int]]) -> int:\n",
    "        n=len(c)\n",
    "        d=[set() for i in range(n)]\n",
    "        for x,y in e: d[x].add(y),d[y].add(x)\n",
    "        q={i for i in range(n) if len(d[i])==1 and c[i]==0}\n",
    "        while q:\n",
    "            x=q.pop()\n",
    "            for y in d[x]:\n",
    "                d[y].remove(x)\n",
    "                if len(d[y])==1 and c[y]==0: q.add(y)\n",
    "            d[x].clear()\n",
    "        for T in range(2):\n",
    "            q=[i for i in range(n) if len(d[i])==1]\n",
    "            for x in q:\n",
    "                for y in d[x]: d[y].remove(x)\n",
    "                d[x].clear()\n",
    "        return (max(sum(len(d[i])>0 for i in range(n)),1)-1)*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n=len(coins)\n",
    "        # if n<=5: return 0\n",
    "        chd=[set() for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            chd[a].add(b)\n",
    "            chd[b].add(a)\n",
    "        l=[i for i in range(n) if len(chd[i])==1]\n",
    "        nl=[]\n",
    "        for nd in l:\n",
    "            while coins[nd]==0 and len(chd[nd])==1:\n",
    "                n-=1\n",
    "                par=chd[nd].pop()\n",
    "                chd[par].remove(nd)\n",
    "                nd=par\n",
    "            if len(chd[nd])==1:\n",
    "                nl.append(nd)\n",
    "        if n<=5: return 0\n",
    "        l=nl\n",
    "        nl=[chd[i].pop() for i in l]\n",
    "        d=Counter(nl)\n",
    "        nl=[k for k,v in d.items() if len(chd[k])<=v+1]\n",
    "        n-=len(l)+len(nl)\n",
    "        res=max(0,n*2-2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        ans = n = len(coins)\n",
    "        degree = [0 for _ in range(n)]\n",
    "        neighbor = [set() for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "            neighbor[x].add(y)\n",
    "            neighbor[y].add(x)\n",
    "        prev = [i for i in range(n) if degree[i] == 1 and coins[i] == 0]\n",
    "        while prev:\n",
    "            cur = prev.copy()\n",
    "            prev = []\n",
    "            for c in cur:\n",
    "                for t in neighbor[c]:\n",
    "                    ans -= 1\n",
    "                    degree[c] -= 1\n",
    "                    degree[t] -= 1\n",
    "                    neighbor[t].remove(c)\n",
    "                    if degree[t] == 1 and coins[t] == 0:\n",
    "                        prev.append(t)\n",
    "        for _ in range(2):\n",
    "            prev = [i for i in range(n) if degree[i] == 1]\n",
    "            for c in prev:\n",
    "                for t in neighbor[c]:\n",
    "                    ans -= 1\n",
    "                    degree[c] -= 1\n",
    "                    degree[t] -= 1\n",
    "                    neighbor[t].remove(c)\n",
    "        return (ans - 1) << 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n=len(coins)\n",
    "        if n<=5: return 0\n",
    "        chd=[set() for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            chd[a].add(b)\n",
    "            chd[b].add(a)\n",
    "        g=[-2]*n\n",
    "        l=[i for i in range(n) if len(chd[i])==1]\n",
    "        res=0\n",
    "        nl=[]\n",
    "        for nd in l:\n",
    "            while coins[nd]==0 and len(chd[nd])==1:\n",
    "                par=chd[nd].pop()\n",
    "                chd[par].remove(nd)\n",
    "                nd=par\n",
    "            if len(chd[nd])==1:\n",
    "                nl.append(nd)\n",
    "        l=nl\n",
    "        st=0\n",
    "        while l:\n",
    "            nl=[]\n",
    "            for nd in l:\n",
    "                g[nd]=st\n",
    "                if len(chd[nd])==0: continue\n",
    "                par=chd[nd].pop()\n",
    "                chd[par].remove(nd)\n",
    "                if len(chd[par])==1:\n",
    "                    nl.append(par)\n",
    "            l=nl\n",
    "            st+=1\n",
    "        res=0\n",
    "        for a,b in edges:\n",
    "            if g[a]>=2 and g[b]>=2:\n",
    "                res+=2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, c: List[int], e: List[List[int]]) -> int:\n",
    "        n=len(c)\n",
    "        d=[set() for i in range(n)]\n",
    "        for x,y in e: d[x].add(y),d[y].add(x)\n",
    "        q={i for i in range(n) if len(d[i])==1 and c[i]==0}\n",
    "        while q:\n",
    "            x=q.pop()\n",
    "            for y in d[x]:\n",
    "                d[y].remove(x)\n",
    "                if len(d[y])==1 and c[y]==0: q.add(y)\n",
    "            d[x].clear()\n",
    "        for T in range(2):\n",
    "            q=[i for i in range(n) if len(d[i])==1]\n",
    "            for x in q:\n",
    "                for y in d[x]: d[y].remove(x)\n",
    "                d[x].clear()\n",
    "        return (max(sum(len(d[i])>0 for i in range(n)),1)-1)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self,coins: List[int],edges:List[List[int]])->int:\n",
    "        def mark_mark_nodes(nodes,mark,spread=False):\n",
    "            for node in nodes.values():\n",
    "                stk=[node]\n",
    "                while len(stk)>0:\n",
    "                    node=stk.pop()\n",
    "                    neigh_alive=[0if 0<nei[1]<mark+spread else 1for nei in node[2]]\n",
    "                    ifmark=sum(neigh_alive) < 2 and (not spread or node[0]==0)\n",
    "                    if node[1]==0 and ifmark:\n",
    "                        node[1]=mark\n",
    "                        if spread:\n",
    "                            stk+=node[2]\n",
    "        nodes={i:[coin,0,[]] for i,coin in enumerate(coins)}\n",
    "        for edge in edges:\n",
    "            i,j=edge[0],edge[1]\n",
    "            nodes[i][2].append(nodes[j])\n",
    "            nodes[j][2].append(nodes[i])\n",
    "        mark_mark_nodes(nodes,1,spread=True)\n",
    "        mark_mark_nodes(nodes,2)\n",
    "        mark_mark_nodes(nodes,3)\n",
    "        return max(0,(sum([node[1]==0 for node in nodes.values()])-1))*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self,coins: List[int],edges:List[List[int]])->int:\n",
    "        def mark_mark_nodes(nodes,mark,spread=False):\n",
    "            for node in nodes.values():\n",
    "                stk=[node]\n",
    "                while len(stk)>0:\n",
    "                    node=stk.pop()\n",
    "                    neigh_alive=[0if 0<nei[1]<mark+spread else 1for nei in node[2]]\n",
    "                    ifmark=sum(neigh_alive) < 2 and (not spread or node[0]==0)\n",
    "                    if node[1]==0 and ifmark:\n",
    "                        node[1]=mark\n",
    "                        if spread:\n",
    "                            stk+=node[2]\n",
    "        nodes={i:[coin,0,[]] for i,coin in enumerate(coins)}\n",
    "        for edge in edges:\n",
    "            i,j=edge[0],edge[1]\n",
    "            nodes[i][2].append(nodes[j])\n",
    "            nodes[j][2].append(nodes[i])\n",
    "        mark_mark_nodes(nodes,1,spread=True)\n",
    "        mark_mark_nodes(nodes,2)\n",
    "        mark_mark_nodes(nodes,3)\n",
    "        return max(0,(sum([node[1]==0 for node in nodes.values()])-1))*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        d = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            d[a].add(b)\n",
    "            d[b].add(a)\n",
    "        for i in range(n):\n",
    "            cur = i\n",
    "            while len(d[cur])==1 and coins[cur]==0:\n",
    "                parent = d[cur].pop()\n",
    "                d[parent].remove(cur)\n",
    "                cur = parent\n",
    "        for _ in range(2):\n",
    "            toRemove = [i for i in range(n) if len(d[i])==1]\n",
    "            for node in toRemove:\n",
    "                if len(d[node])==1:\n",
    "                    parent = d[node].pop()\n",
    "                    d[parent].remove(node)\n",
    "        return sum(len(d[key]) for key in d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        # 叶子上如果无金币，可以移除。\n",
    "        g = defaultdict(set)\n",
    "        n = len(coins)\n",
    "        degs = [0] * n  # 度数\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "            degs[a] += 1\n",
    "            degs[b] += 1\n",
    "\n",
    "        def remove_leaf(anyway):\n",
    "            q = deque()\n",
    "\n",
    "            for i, v in enumerate(degs):\n",
    "                if v == 1 and (anyway or coins[i] == 0):\n",
    "                    q.append(i)\n",
    "            while q:\n",
    "                i = q.popleft()\n",
    "                if anyway or coins[i] == 0:\n",
    "                    degs[i] = 0\n",
    "                    for nxt in g[i]:\n",
    "                        g[nxt].discard(i)\n",
    "                        degs[nxt] -= 1\n",
    "                        if degs[nxt] == 1 and (not anyway and coins[nxt] == 0):\n",
    "                            q.append(nxt)\n",
    "                del g[i]\n",
    "\n",
    "        remove_leaf(False)\n",
    "        remove_leaf(True)\n",
    "        remove_leaf(True)\n",
    "\n",
    "        ans = 0\n",
    "        for a, b in g.items():\n",
    "            ans += len(b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        ind = defaultdict(int)\n",
    "\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "            ind[a] += 1\n",
    "            ind[b] += 1\n",
    "\n",
    "        q = deque()\n",
    "\n",
    "        nodes = set(range(n))\n",
    "\n",
    "        for x in range(n):\n",
    "            if ind[x] == 1 and coins[x] == 0:\n",
    "                q.append(x)\n",
    "\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            nodes.remove(x)\n",
    "\n",
    "            for y in g[x]:\n",
    "                ind[y] -= 1\n",
    "                if ind[y] == 1 and coins[y] == 0:\n",
    "                    q.append(y)\n",
    "\n",
    "        # print(nodes)\n",
    "\n",
    "        q = []\n",
    "        for x in list(nodes):\n",
    "            if ind[x] == 1:\n",
    "                q.append(x)\n",
    "\n",
    "        for _ in range(2):\n",
    "            p = []\n",
    "            for x in q:\n",
    "                nodes.remove(x)\n",
    "                for y in g[x]:\n",
    "                    ind[y] -= 1\n",
    "                    if ind[y] == 1:\n",
    "                        p.append(y)\n",
    "\n",
    "            q = p\n",
    "\n",
    "        # print(nodes)\n",
    "\n",
    "        if len(nodes) == 0:\n",
    "            return 0\n",
    "        \n",
    "        return 2 * (len(nodes) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = coins.__len__()\n",
    "        mmap = {}\n",
    "        for i in range(n):\n",
    "            mmap[i] = {}\n",
    "        for i in range(edges.__len__()):\n",
    "            x = edges[i][0]\n",
    "            y = edges[i][1]\n",
    "            mmap[x][y] = 1\n",
    "            mmap[y][x] = 1\n",
    "\n",
    "        dele = [0] * coins.__len__()\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if mmap[i].__len__() == 1 and coins[i] == 0:\n",
    "                q.append(i)\n",
    "        while q.__len__() != 0:\n",
    "            now = q.pop(0)\n",
    "            dele[now] = 1\n",
    "            for nes in mmap[now].keys():\n",
    "                mmap[nes].pop(now)\n",
    "                if mmap[nes].__len__() == 1 and coins[nes] == 0:\n",
    "                    q.append(nes)\n",
    "\n",
    "        for i in range(2):\n",
    "            for i in range(n):\n",
    "                if not dele[i] and mmap[i].__len__() == 1:\n",
    "                    dele[i] = 1\n",
    "\n",
    "            for i in range(n):\n",
    "                if dele[i]:\n",
    "                    for nes in mmap[i].keys():\n",
    "                        if i in mmap[nes].keys():\n",
    "                            mmap[nes].pop(i)\n",
    "        res = 0\n",
    "        for i in range(edges.__len__()):\n",
    "            x = edges[i][0]\n",
    "            y = edges[i][1]\n",
    "            if not dele[x] and not dele[y]:\n",
    "                res += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\r\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\r\n",
    "        # - 按照其思路, 转成py代码\r\n",
    "        # * 构建邻接表/邻接矩阵, 二者任选其一即可\r\n",
    "        neibors = defaultdict(set)\r\n",
    "        N = len(coins)\r\n",
    "        for a, b in edges:\r\n",
    "            neibors[a].add(b)\r\n",
    "            neibors[b].add(a)\r\n",
    "\r\n",
    "        # - 01. 删除所有无金币的叶子节点, 直到树中所有叶子节点都是有金币的\r\n",
    "        # * 构建节点删除查询表\r\n",
    "        deleted = [0] * N\r\n",
    "        # * 记录可删节点\r\n",
    "        q = deque()\r\n",
    "        for i in range(N):\r\n",
    "            if len(neibors[i]) == 1 and coins[i] == 0:\r\n",
    "                q.append(i)\r\n",
    "        # * 开删, 同时加入新的可删节点\r\n",
    "        while q:\r\n",
    "            cur = q.popleft()\r\n",
    "            deleted[cur] = 1\r\n",
    "            for ne in neibors[cur]:\r\n",
    "                # * 删除与该节点的邻接关系\r\n",
    "                # neibors[ne].discard(cur)\r\n",
    "                neibors[ne].remove(cur)\r\n",
    "                # * 查询是否为新的无金币叶子节点\r\n",
    "                if len(neibors[ne]) == 1 and coins[ne] == 0:\r\n",
    "                    q.append(ne)\r\n",
    "            neibors[cur].clear()\r\n",
    "\r\n",
    "        # - 02. 不用管金币, 删除最外支的两层叶子节点, 因为他们不必访问\r\n",
    "        for _ in range(2):\r\n",
    "            for i in range(N):\r\n",
    "                # * 1. 要求该节点没删, 2. 要求该节点是叶子节点\r\n",
    "                if not deleted[i] and len(neibors[i]) == 1:\r\n",
    "                    deleted[i] = 1\r\n",
    "            # * 开删, 操作一样\r\n",
    "            for i in range(N):\r\n",
    "                if deleted[i]:\r\n",
    "                    for ne in neibors[i]:\r\n",
    "                        # neibors[ne].discard(i)\r\n",
    "                        neibors[ne].remove(i)\r\n",
    "                    neibors[i].clear()\r\n",
    "\r\n",
    "        # - 03. 删完后, 剩余的边就是所有要走的路径, 注意最终要回到原点, 在没环的条件下, 每条边都得一去一回(记录2次)\r\n",
    "        # ! 这里要注意, 如果说是一颗树的话, 就不会出现图中的环(无向无根树)\r\n",
    "        return sum(2 for e in edges\r\n",
    "                   if deleted[e[0]] == 0 and deleted[e[1]] == 0)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        dd = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            dd[a].add(b)\n",
    "            dd[b].add(a)\n",
    "        # 第一次遍历，裁剪所有无金币的叶子节点\n",
    "        q = deque([k for k, v in dd.items() if len(v) == 1])\n",
    "        while q:\n",
    "            k = q.popleft()\n",
    "            if not coins[k]:\n",
    "                for nei in dd[k]:\n",
    "                    dd[nei].discard(k)\n",
    "                    if len(dd[nei]) == 1:\n",
    "                        q.append(nei)\n",
    "                dd.pop(k)\n",
    "        # 第二次遍历\n",
    "        q = deque([k for k, v in dd.items() if len(v) == 1])\n",
    "        for i in range(2):\n",
    "            length = len(q)\n",
    "            for j in range(length):\n",
    "                k = q.popleft()\n",
    "                for nei in dd[k]:\n",
    "                    dd[nei].discard(k)\n",
    "                    if len(dd[nei]) == 1:\n",
    "                        q.append(nei)\n",
    "                dd.pop(k)\n",
    "        remain = max(0, len(dd) - 1)\n",
    "        return 2 * remain\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 参考 https://leetcode.cn/problems/collect-coins-in-a-tree/solutions/2191371/tuo-bu-pai-xu-ji-lu-ru-dui-shi-jian-pyth-6uli/?envType=daily-question&envId=2023-09-21\n",
    "# 核心是拓朴排序，排序规则为相邻节点个数。第一步是剪枝，去掉没有金币的叶子节点。第二步使用两次循环剪掉有金币的叶子节点范围2以内的所有节点。第三步是根据剩余节点计算通过的路径数。\n",
    "from collections import defaultdict, deque\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        dd = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            dd[a].add(b)\n",
    "            dd[b].add(a)\n",
    "        # 第一次遍历，裁剪所有无金币的叶子节点\n",
    "        q = deque([k for k, v in dd.items() if len(v) == 1])\n",
    "        while q:\n",
    "            k = q.popleft()\n",
    "            if not coins[k]:\n",
    "                for nei in dd[k]:\n",
    "                    dd[nei].discard(k)\n",
    "                    if len(dd[nei]) == 1:\n",
    "                        q.append(nei)\n",
    "                dd.pop(k)\n",
    "        # 第二次遍历\n",
    "        q = deque([k for k, v in dd.items() if len(v) == 1])\n",
    "        for i in range(2):\n",
    "            length = len(q)\n",
    "            for j in range(length):\n",
    "                k = q.popleft()\n",
    "                for nei in dd[k]:\n",
    "                    dd[nei].discard(k)\n",
    "                    if len(dd[nei]) == 1:\n",
    "                        q.append(nei)\n",
    "                dd.pop(k)\n",
    "        remain = max(0, len(dd) - 1)\n",
    "        return 2 * remain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n=len(coins)\n",
    "        dic=defaultdict(set)\n",
    "        vis=[0]*n\n",
    "        for x,y in edges:\n",
    "            dic[x].add(y)\n",
    "            dic[y].add(x)\n",
    "        cnt=0\n",
    "        q=deque([])\n",
    "        for k in dic:\n",
    "            if len(dic[k])==1 and coins[k]==0:\n",
    "                q.append(k)\n",
    "        while q:\n",
    "            p=q.popleft()#(0)\n",
    "            vis[p]=1\n",
    "            if dic[p]:\n",
    "                k=dic[p].pop()\n",
    "                dic[k].discard(p)\n",
    "                if len(dic[k])==1 and coins[k]==0:\n",
    "                    q.append(k)\n",
    "        for _ in range(2):\n",
    "            q=deque([])\n",
    "            for k in dic:\n",
    "                if len(dic[k])==1:\n",
    "                    q.append(k)\n",
    "            while q:\n",
    "                p=q.popleft()#pop(0)\n",
    "                vis[p]=1\n",
    "                if dic[p]:\n",
    "                    k=dic[p].pop()\n",
    "                    dic[k].discard(p)\n",
    "        a=sum(vis)\n",
    "        if a==n: return 0\n",
    "        return 2*(n-a-1)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 参考 https://leetcode.cn/problems/collect-coins-in-a-tree/solutions/2191371/tuo-bu-pai-xu-ji-lu-ru-dui-shi-jian-pyth-6uli/?envType=daily-question&envId=2023-09-21\n",
    "# 核心是拓朴排序，排序规则为相邻节点个数。第一步是剪枝，去掉没有金币的叶子节点。第二步使用两次循环剪掉有金币的叶子节点范围2以内的所有节点。第三步是根据剩余节点计算通过的路径数。\n",
    "from collections import defaultdict, deque\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        # 构建拓扑结构\n",
    "        dd = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            dd[a].add(b)\n",
    "            dd[b].add(a)\n",
    "        # 第一次遍历，裁剪所有无金币的叶子节点\n",
    "        q = deque([k for k, v in dd.items() if len(v) == 1])\n",
    "        while q:\n",
    "            k = q.popleft()\n",
    "            if not coins[k]:\n",
    "                for nei in dd[k]:\n",
    "                    dd[nei].discard(k)\n",
    "                    if len(dd[nei]) == 1:\n",
    "                        q.append(nei)\n",
    "                dd.pop(k)\n",
    "        # 第二次遍历， 裁剪有金币的叶子节点范围2以内的所有节点\n",
    "        q = deque([k for k, v in dd.items() if len(v) == 1])\n",
    "        for i in range(2):\n",
    "            length = len(q)\n",
    "            for j in range(length):\n",
    "                k = q.popleft()\n",
    "                for nei in dd[k]:\n",
    "                    dd[nei].discard(k)\n",
    "                    if len(dd[nei]) == 1:\n",
    "                        q.append(nei)\n",
    "                dd.pop(k)\n",
    "        remain = max(0, len(dd) - 1)\n",
    "        return 2 * remain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        n = len(coins)\n",
    "        q = deque(i for i in range(n) if len(g[i]) == 1 and coins[i] == 0)\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            for j in g[i]:\n",
    "                g[j].remove(i)\n",
    "                if coins[j] == 0 and len(g[j]) == 1:\n",
    "                    q.append(j)\n",
    "            g[i].clear()\n",
    "        for k in range(2):\n",
    "            q = [i for i in range(n) if len(g[i]) == 1]\n",
    "            for i in q:\n",
    "                for j in g[i]:\n",
    "                    g[j].remove(i)\n",
    "                g[i].clear()\n",
    "        return sum(len(g[a]) > 0 and len(g[b]) > 0 for a, b in edges) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        n = len(coins)\n",
    "        q = deque(i for i in range(n) if len(g[i]) == 1 and coins[i] == 0)\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            for j in g[i]:\n",
    "                g[j].remove(i)\n",
    "                if coins[j] == 0 and len(g[j]) == 1:\n",
    "                    q.append(j)\n",
    "            g[i].clear()\n",
    "        for k in range(2):\n",
    "            q = [i for i in range(n) if len(g[i]) == 1]\n",
    "            for i in q:\n",
    "                for j in g[i]:\n",
    "                    g[j].remove(i)\n",
    "                g[i].clear()\n",
    "        return sum(len(g[a]) > 0 and len(g[b]) > 0 for a, b in edges) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        # 转换为邻接表\n",
    "        # g[i]表示节点i的所有邻接节点，用集合表示\n",
    "        g = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        \n",
    "        # 遍历所有节点，找到coins[i]=0且g[i]只有一个节点的节点\n",
    "        # 即金币为0的叶子节点，加入q中\n",
    "        n = len(coins)\n",
    "        q = deque(i for i in range(n) if len(g[i]) == 1 and coins[i] == 0)\n",
    "\n",
    "        # 不断从队列中取出节点，将其从邻接表中删除\n",
    "        # 判断邻接节点是否满足coins[j] = 0且g[j]中只有一个节点的条件，满足则加入队列q中，循环直至队列为空\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            for j in g[i]:\n",
    "                g[j].remove(i)\n",
    "                if coins[j] == 0 and len(g[j]) == 1:\n",
    "                    q.append(j)\n",
    "            g[i].clear()\n",
    "        \n",
    "        # 得到一颗新的树，且叶子节点金币都为1\n",
    "        # 删除剩下两层叶子节点，最终得到一颗所有节点都需要被访问\n",
    "        # 统计边数*2即可\n",
    "        for k in range(2):\n",
    "            q = [i for i in range(n) if len(g[i]) == 1]\n",
    "            for i in q:\n",
    "                for j in g[i]:\n",
    "                    g[j].remove(i)\n",
    "                g[i].clear()\n",
    "        return sum(len(g[a]) > 0 and len(g[b]) > 0 for a,b in edges) * 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        n = len(coins)\n",
    "        q = deque(i for i in range(n) if len(g[i]) == 1 and coins[i] == 0)\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            for j in g[i]:\n",
    "                g[j].remove(i)\n",
    "                if coins[j] == 0 and len(g[j]) == 1:\n",
    "                    q.append(j)\n",
    "            g[i].clear()\n",
    "        for k in range(2):\n",
    "            q = [i for i in range(n) if len(g[i]) == 1]\n",
    "            for i in q:\n",
    "                for j in g[i]:\n",
    "                    g[j].remove(i)\n",
    "                g[i].clear()\n",
    "        return sum(len(g[a]) > 0 and len(g[b]) > 0 for a, b in edges) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        n = len(coins)\n",
    "        q = deque(i for i in range(n) if len(g[i]) == 1 and coins[i] == 0)\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            for j in g[i]:\n",
    "                g[j].remove(i)\n",
    "                if len(g[j]) == 1 and coins[j] == 0:\n",
    "                    q.append(j)\n",
    "            g[i].clear()\n",
    "        for k in range(2):\n",
    "            end_list = [i for i in range(n) if len(g[i]) == 1]\n",
    "            for i in end_list:\n",
    "                for j in g[i]:\n",
    "                    g[j].remove(i)\n",
    "                g[i].clear()\n",
    "        return sum(len(g[a])>0 and len(g[b])>0 for a, b in edges)*2\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        # n = len(edges)\n",
    "        # if n <= 3:\n",
    "        #     return 0\n",
    "        e = collections.defaultdict(set)\n",
    "        grad = collections.defaultdict(int)\n",
    "        for x, y in edges:\n",
    "            e[x].add(y)\n",
    "            e[y].add(x)\n",
    "            grad[x] += 1\n",
    "            grad[y] += 1\n",
    "            \n",
    "        q = deque()\n",
    "        for k, v in grad.items():\n",
    "            if v == 1 and coins[k] == 0:\n",
    "                q.append(k)\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            if grad[tmp] == 1:\n",
    "                grad[tmp] -= 1\n",
    "                ne = e[tmp].pop()\n",
    "                grad[ne] -= 1\n",
    "                if grad[ne] == 1 and coins[ne] == 0:\n",
    "                    q.append(ne)\n",
    "                e[ne].remove(tmp)\n",
    "        # print(e)\n",
    "        # print(grad)\n",
    "        q = deque()\n",
    "        for k, v in grad.items():\n",
    "            if v == 1:\n",
    "                q.append(k)\n",
    "        # print(\"q2\", q)\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            if grad[tmp] == 1:\n",
    "                grad[tmp] -= 1\n",
    "                ne = e[tmp].pop()\n",
    "                grad[ne] -= 1\n",
    "                e[ne].remove(tmp)\n",
    "            \n",
    "        # print(e)\n",
    "        # print(grad)\n",
    "        \n",
    "        q = deque()\n",
    "        for k, v in grad.items():\n",
    "            if v == 1:\n",
    "                q.append(k)\n",
    "        # print(\"q3\", q)\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            if grad[tmp] == 1:\n",
    "                grad[tmp] -= 1\n",
    "                ne = e[tmp].pop()\n",
    "                grad[ne] -= 1\n",
    "                e[ne].remove(tmp)\n",
    "            \n",
    "        # print(e)\n",
    "        # print(grad)\n",
    "        # for k, v in grad.items():\n",
    "        #     print(k, v)\n",
    "        #     if v == 1:\n",
    "        #         grad[k] -= 1\n",
    "        #         for ne in e[k]:\n",
    "        #             grad[ne] -= 1\n",
    "        #             e[ne].remove(k)\n",
    "        #         del e[k]\n",
    "        # print(e)\n",
    "        # print(grad)\n",
    "        # for k, v in grad.items():\n",
    "        #     if v == 1:\n",
    "        #         grad[k] -= 1\n",
    "        #         del e[k]\n",
    "        #         for ne in e[k]:\n",
    "        #             grad[ne] -= 1\n",
    "        #             e[ne].remove(k)\n",
    "        cnt = 0\n",
    "        for k, v in grad.items():\n",
    "            if v != 0:\n",
    "                cnt += 1\n",
    "        # print(cnt)\n",
    "        return 2 * (cnt - 1) if cnt >= 1 else 0\n",
    "                \n",
    "        \n",
    "           \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        d = [0] * n\n",
    "        s = defaultdict(set)\n",
    "        for i,j in edges:\n",
    "            d[i] += 1\n",
    "            d[j] += 1\n",
    "            s[i].add(j)\n",
    "            s[j].add(i)\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if d[i] == 1 and coins[i] == 0:\n",
    "                q.append(i)\n",
    "        ans = n\n",
    "        while q:\n",
    "            i = q.pop()\n",
    "            print(i)\n",
    "            d[i] -= 1\n",
    "            ans -= 1\n",
    "            for j in s[i]:\n",
    "                if d[j] > 0:\n",
    "                    d[j] -= 1\n",
    "                    if d[j] == 1 and coins[j] == 0:\n",
    "                        q.append(j)\n",
    "        print('111')\n",
    "        for i in range(n):\n",
    "            if d[i] == 1:\n",
    "                print(i)\n",
    "                ans -= 1\n",
    "                q.append(i)\n",
    "        for i in q:\n",
    "            for j in s[i]:\n",
    "                if d[j] > 0:\n",
    "                    d[j] -= 1\n",
    "                    if d[j] == 1:\n",
    "                        ans -= 1\n",
    "        return max((ans - 1) * 2,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(coins)\n",
    "        d = [0] * n\n",
    "        s = defaultdict(set)\n",
    "        for i,j in edges:\n",
    "            d[i] += 1\n",
    "            d[j] += 1\n",
    "            s[i].add(j)\n",
    "            s[j].add(i)\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if d[i] == 1 and coins[i] == 0:\n",
    "                q.append(i)\n",
    "        ans = n\n",
    "        while q:\n",
    "            i = q.pop()\n",
    "            d[i] -= 1\n",
    "            ans -= 1\n",
    "            for j in s[i]:\n",
    "                if d[j] > 0:\n",
    "                    d[j] -= 1\n",
    "                    if d[j] == 1 and coins[j] == 0:\n",
    "                        q.append(j)\n",
    "        for i in range(n):\n",
    "            if d[i] == 1:\n",
    "                ans -= 1\n",
    "                q.append(i)\n",
    "        for i in q:\n",
    "            for j in s[i]:\n",
    "                if d[j] > 0:\n",
    "                    d[j] -= 1\n",
    "                    if d[j] == 1:\n",
    "                        ans -= 1\n",
    "        return max((ans - 1) * 2,0)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
